Game of Swapping Numbers

題意：

A，B兩個數組，讓你對A進行k次操作，每次操作為選兩個位置的數，進行交換，求最大化的Σ|Ai-Bi|

題解：

以前有做過最小化的情況，就是把每次交換作定量分析
我們現在考慮Ai，Aj，Bi，Bj的情況
設xi=min(Ai,Bi),yi=max(Ai,Bi)
xj=min(Aj,Bj),yi=max(Aj,Bj)
也就是后者一定大于前者
(xi,yi),(xj,yj)
我們對x和y都已經單獨排序，保證xi<xj(i<j)
xi<yi,xj<yj,xi<xj,yi<yj
當前答案為：ans = |xi-yi|+|xj-yj| = yi - xi + yj - xj
現在我們考慮將bi和bj進行交換，看看答案會有什么變化
i<j
(xi,yj),(xj,yi)
已知：xi<yi<yj
ans = |xi-yj| + |xj-yi| = yj-xi+|xj-yi|
如果xj<yi,ans1=yj - xi + yi -xj
ans-ans1 = 0
如果xj>yi，ans1 = yj - xi + xj - yi
ans-ans1 = 2yi - 2xi
ans + （2xi - 2yi）= ans1
也就是會有（2xi - 2yi）的變化，要想有更大的變化，我們可以讓xi逆序排，也就是讓更大的xi減更小的yi，當然要讓（2xi - 2yi）的值大于0值才有效。

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e5+9; int a[maxn],b[maxn]; bool cmp(int a,int 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;for(int i=1;i<=n;i++){if(a[i]>b[i])swap(a[i],b[i]);ans+=abs(a[i]-b[i]);}sort(a+1,a+1+n,cmp);sort(b+1,b+1+n);for(int i=1;i<=n;i++){if(k==0)break;int tmp=2*a[i]-2*b[i];if(tmp>0)ans+=tmp;else break;k--;}cout<<ans;return 0; }

總結

以上是生活随笔為你收集整理的Game of Swapping Numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。