又双叒叕水了一篇题解…
题目简述
对于两个序列 A，序列 B，长度一致；
共 次操作，
每次操作都会向这两个序列增加数字。
在每次操作后，要求对每个序列中的每个数字配对，要让配对数之和的最大值最小。
Solution
贪心。
对每时每刻的序列排序， 中从小到大与 中从大到小配对。
证明：
对于序列中最小的 ，序列最大的，
若将 替换成 且 ，此时必有 ，不必原计划更优；
若将 替换成 ，且 ，则必有 需要与 配对。所以必有更大值 ，也不必原计划更优。
所以，每次选择最小和最大的配对可以得到最优解。
可惜直接排序时间复杂度不够。
时间复杂度为 ，，超时。
优化。
1、桶优化
发现 ，所以考虑直接桶排。
时间复杂度降为 。
2、连续配对优化
发现当 出现多次时，会直接配出 组一样的配对。
所以对于桶中 ，每次配对时，对应减少 即可。
最坏时间复杂度为 ，不会超时。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
int a[101],b[101];
int am[101],bm[101];
int main()
{
int n,k,maxn=-414231;
cin>>n;
for(int i=1;i<=n;i++)
{
maxn=-414231;
cin>>k,am[k]++;
cin>>k,bm[k]++;
memcpy(a,am,sizeof(am));
memcpy(b,bm,sizeof(bm));
int l=1,r=100;
while(r>=1&&l<=100)
{
while(!a[l]) l++;
while(!b[r]) r--;
if(r<1||l>100) break;
maxn=max(maxn,l+r);
minx=min(a[l],b[r]);
a[l]-=minx;b[r]-=minx;
}
cout<<maxn<<endl;
}
return 0;
}
|
qwq