题意:给与两个长度为n的a,b数组,你可以交换a数组中两个元素位置,你恰好进行k次操作后 的最大值?
思路:
首先我们思考一下什么样的两个数交换后的结果会大:
假如有两对数:(a1,b1),(a2,b2)
原结果为abs(a1-b1)+abs(a2-b2)
如果a1>b1&&a2>b2&&b1>a2:
那么原结果为abs(a1-b1)+abs(a2-b2)=a1+a2-b1-b2
交换后结果为:abs(a1-b2)+abs(a2-b1)=a1-b2+b1-a2=a1+b1-a2-b2
结果之差为2 * b1 - 2 * a2=2*min(a1,b1)-2 * max(a2,b2)
如果a1>b1&&a2>b2&&b1<a2:
那么原结果为abs(a1-b1)+abs(a2-b2)=a1+a2-b1-b2
交换后结果为:abs(a1-b2)+abs(a2-b1)=a1-b2+a2-b1=a1+a2-b1-b2
结果之差为0
如此分析下去:
我们发现可以使结果增长的情况为一对的最小值大于另一对的最大值时.
然后当n>2时,最优解结果(a1,b1),(a2,b2),(a3,b3).........其中ai<bi或者ai>bi的对数一定有一种有两对,假如这两对为(a1,b1),(a2,b2) {a1>b1&&a2>b2}如上分析要么增加要么不变,所以恰好为k在n>2时等价于小于等于k次,所以加上可以增加的情况并小于等于k次即可。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+7; ll a[N], b[N], Ma[N], Mi[N]; bool cmp(ll a,ll b) { return a>b; } int main() { int n, k; cin >> n >> k; for(int i {1}; i<=n; i++) { cin >> a[i]; } for(int i {1}; i<=n; i++) { cin >> b[i]; } ll ans=0; if(n==2) { if(k%2) { swap(a[1],a[2]); } ans=ans+abs(a[1]-b[1])+abs(a[2]-b[2]); } else { for(int i=1;i<=n;i++) { ans=ans+abs(a[i]-b[i]); Ma[i]=max(a[i],b[i]); Mi[i]=min(a[i],b[i]); } sort(Mi+1,Mi+n+1,cmp); sort(Ma+1,Ma+n+1); for(int i=1;i<=k&&i<=n;i++) { if(Mi[i]>Ma[i]) { ans=ans+2*(Mi[i]-Ma[i]); } else { break; } } } cout << ans << endl; return 0; }