题解：P14029 【MX-X20-T3】「FAOI-R7」重排序列（update）

该做法与第一篇题解略有不同。

已知

(a+b) \bmod m = (a \bmod m) + (b \bmod m ) \bmod m

，我们将

a,b

序列中所有数对

m

取模，那么

a_i+b_i

的值域为

[0,2m]

。

理想情况下，对于所有

i

有

a_i+b_i<m

，那么和为

\sum^n_i (a_i+b_i)

。但显然我们可能会有某些位置

i

有

a_i+b_i \ge m

，此时贡献变成了

a_i+b_i-m

。对比理想状况，位置

i

产生的贡献减少了

(a_i+b_i)-(a_i+b_i-m) = m

，

m

是给定常数，问题就转化成如何排列使得

a+b \ge m

的情况最少。

将

a

降序排序，

b

升序排序，

a_i

在递减过程中，

b

中满足

a_i+b_j<m

的区间会向右扩展，我们不难发现此时

a_i

去匹配最小的

b_j

是最优的。如果

a_i

怎么匹配都匹配不到

a_i+a_j<m

，那就只能去和最大的

b_j

匹配，将更小的

b_j

留给后面的数。

时间复杂度

O(n \log n)

。

CPP

# include <bits/stdc++.h>

using namespace std;

struct arr{
	long long v;
	long long new_v;
	int idx;
};
arr arr1[200005];
arr arr2[200005];

bool cmp1(arr a,arr b) {return a.new_v > b.new_v;}
bool cmp2(arr a,arr b) {return a.new_v < b.new_v;}
bool cmp3(arr a,arr b) {return a.idx < b.idx;}

void solve()
{
	int n,m;
	scanf ("%d %d",&n,&m);
	
	for (int i=0;i<n;i++) scanf ("%lld",&arr1[i].v);
	for (int i=0;i<n;i++) scanf ("%lld",&arr2[i].v);
	for (int i=0;i<n;i++) 
	{
		arr1[i].idx = i;
		arr2[i].idx = i;
		arr1[i].new_v=arr1[i].v%m;
		arr2[i].new_v=arr2[i].v%m;
	}
	
	sort(arr1,arr1+n,cmp1);
	sort(arr2,arr2+n,cmp2);
	
	long long ans=0;
	int l=0,r=n-1;
	for (int i=0;i<n;i++)
	{
		if (arr1[i].new_v + arr2[l].new_v >= m) 
		{
			ans += (arr1[i].new_v + arr2[r].new_v) % m;
			arr2[r--].idx = arr1[i].idx;	
		}
		else
		{
			ans += (arr1[i].new_v + arr2[l].new_v) % m;
			arr2[l++].idx = arr1[i].idx;
		}
	}
	
	sort(arr2,arr2+n,cmp3);
	
	printf ("%lld\n",ans);
	for (int i=0;i<n;i++) printf ("%lld ",arr2[i].v);
	printf ("\n");
	return ;
}

int main (void)
{
	int T;
	scanf ("%d",&T);
	
	while (T--)
	{
		solve();	
	}
	return 0;
}

题解：P14029 【MX-X20-T3】「FAOI-R7」重排序列（update）

文章操作

相关推荐

评论

题解：P14029 【MX-X20-T3】「FAOI-R7」重排序列（update）