栖霞建设招标网站,网上怎么开网店创业,自做刷赞网站,wordpress主题公众号Game of Swapping Numbers
题意#xff1a;
A#xff0c;B两个数组#xff0c;让你对A进行k次操作#xff0c;每次操作为选两个位置的数#xff0c;进行交换#xff0c;求最大化的Σ|Ai-Bi|
题解#xff1a;
以前有做过最小化的情况#xff0c;就是把每次交换作定量…Game of Swapping Numbers
题意
AB两个数组让你对A进行k次操作每次操作为选两个位置的数进行交换求最大化的Σ|Ai-Bi|
题解
以前有做过最小化的情况就是把每次交换作定量分析 我们现在考虑AiAjBiBj的情况 设ximin(Ai,Bi),yimax(Ai,Bi) xjmin(Aj,Bj),yimax(Aj,Bj) 也就是后者一定大于前者 (xi,yi),(xj,yj) 我们对x和y都已经单独排序保证xixj(ij) xiyi,xjyj,xixj,yiyj 当前答案为ans |xi-yi||xj-yj| yi - xi yj - xj 现在我们考虑将bi和bj进行交换看看答案会有什么变化 ij (xi,yj),(xj,yi) 已知xiyiyj ans |xi-yj| |xj-yi| yj-xi|xj-yi| 如果xjyi,ans1yj - xi yi -xj ans-ans1 0 如果xjyians1 yj - xi xj - yi ans-ans1 2yi - 2xi ans 2xi - 2yi ans1 也就是会有2xi - 2yi的变化要想有更大的变化我们可以让xi逆序排也就是让更大的xi减更小的yi当然要让2xi - 2yi的值大于0值才有效。
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn5e59;
int a[maxn],b[maxn];
bool cmp(int a,int b){return ab;
}
int main()
{int n,k;cinnk;for(int i1;in;i){cina[i];}for(int i1;in;i){cinb[i];}ll ans0;for(int i1;in;i){if(a[i]b[i])swap(a[i],b[i]);ansabs(a[i]-b[i]);}sort(a1,a1n,cmp);sort(b1,b1n);for(int i1;in;i){if(k0)break;int tmp2*a[i]-2*b[i];if(tmp0)anstmp;else break;k--;}coutans;return 0;
}
