@codeforces - 1214F@ Employment

深碍√TFBOYSˉ_ 2023-06-01 12:58 3阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

有 m 个城市围成一个圆环，编号为 1~m。  
某公司有 n 个职员住在 m 个城市，依次住在编号为 a1, a2, ..., an 的城市（可能住在同一城市）。且该公司有 n 个工作场所，依次在 b1, b2, ..., bn（一样可以在同一城市）。  
现在要将职员与城市一一匹配，使得每个职员的居所与工作场所距离之和最小，并输出方案。

**Input**  
第一行两个整数 m, n（1 <= m <= 10^9, 1 <= n <= 200000），表示圆环上的城市个数以及职员个数。  
第二行 n 个整数 a1, a2, ..., an（1 <= ai <= m），表示职员居住的城市编号  
第三行 n 个整数 b1, b2, ..., bn（1 <= bi <= m），表示工作场所所在的城市编号。

**Output**  
第一行输出最小距离总和。  
第二行输出匹配方案，第 i 个数表示第 i 个职员工作的场所编号。

**Examples**  
**Input**  
10 3  
1 5 5  
10 4 6  
**Output**  
3  
1 2 3

**Input**  
10 3  
1 4 8  
8 3 6  
**Output**  
4  
2 3 1

**Note**  
第一个样例中，1 - 10, 5 - 4, 5 - 6 的距离都为 1。  
第二个样例中，1 - 3, 4 - 6, 8 - 8 的距离分别为 2, 2, 0。

## @solution@ ##

[巧妙地见过类似的原题][Link 1]。。。  
然而我在考场上还是没有做出来，真是丢人。

先将 a, b 排好序。  
首先将 bi 扩张成三倍，分别为 bi - m, bi, bi + m。则 ai 与 bj 之间在圆环上的距离肯定为 ai 到 bj - m, bj, bj + m 之中的某一个的数轴上的距离。  
记这个扩张过后的 b 为 b‘。

假如一个方案中 ai 匹配 bx，aj 匹配 by，且 ai < aj, bx > by（即匹配出现交叉），则交换匹配变成 ai 匹配 by，aj 匹配 bx 会更优（分类讨论众多情况即可验证）。  
同时还可以在原先的圆环上验证一个结论：如果 a1 匹配 b\[x\]，则 a2 应依次匹配 b\[x+1\]，a3 匹配 b\[x+2\]，...。

贪心地得到了这两个结论后，我们最终有效的方案只有 2\*n + 1 种。只要能有效地维护出每种方案的距离总和就可以解决这道题。  
定义 ans\[i\] 表示 a1 匹配 i 的距离总和。

两个点 i, j 的距离定义为 |i - j|，其中 i >= j 时为 i - j，否则为 j - i。  
一开始 a1 匹配 b1，匹配的点对之间距离总为 ai - bi。将 a1 对应的匹配往后移动时，ai - bj 就将变为 bj - ai。  
于是对于每一个 ai，对一开始某个连续的区间的贡献为 +ai，对后面某个连续的区间的贡献为 -ai；bi 对一开始某个连续的区间的贡献 -bi，对后面某个连续的区间的贡献为 +bi。  
找出那个变化的点（即 b\[j\] <= a\[i\] < b\[j+1\]），做一个差分即可。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 200000; const ll INF = (1LL<<60); struct node{ int pos; ll key; friend bool operator < (node a, node b) { return a.key < b.key; } }a[MAXN + 5], b[3*MAXN + 5]; ll sum[3*MAXN + 5]; int res[MAXN + 5]; int n; ll m; int main() { scanf("%lld%d", &m, &n); for(int i=1;i<=n;i++) scanf("%d", &a[i].key), a[i].pos = i; sort(a + 1, a + n + 1); a[n + 1].key = INF; for(int i=1;i<=n;i++) scanf("%d", &b[i].key), b[i].pos = i; sort(b + 1, b + n + 1); for(int i=1;i<=n;i++) { b[2*n + i] = b[n + i] = b[i]; b[i].key -= m, b[2*n + i].key += m; } int p = 1; for(int i=1;i<=n;i++) { while( b[p].key <= a[i].key ) p++; sum[0] += a[i].key; if( p - i + 1 <= 2*n + 1 ) sum[p - i + 1] -= 2*a[i].key; } p = 1; for(int i=1;i<=3*n;i++) { while( a[p].key < b[i].key ) p++; sum[max(0, i - n + 1)] -= b[i].key; if( i - p + 2 <= 2*n + 1 ) sum[i - p + 2] += 2*b[i].key; sum[min(i + 1, 2*n + 2)] -= b[i].key; } int ans = 1; for(int i=1;i<=2*n+1;i++) { sum[i] += sum[i-1]; if( sum[i] < sum[ans] ) ans = i; } for(int i=1;i<=n;i++) res[a[i].pos] = b[ans+i-1].pos; printf("%lld\n", sum[ans]); for(int i=1;i<=n;i++) printf("%d ", res[i]); }

## @details@ ##

当时在网上随便找了一个题解，改改改写写写结果怎样都过不了。

后来自己一写就过了 =\_=。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11553029.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6364