牛客多校1、Game of Swapping Numbers

https://ac.nowcoder.com/acm/contest/11166/G

题意:现在有两个长度为n的数组a,b,最多可以对a数组进行m次交换,需要使得牛客多校1、Game of Swapping Numbers

最大。

思路: 首先我们知道最多交换n次就可以使得结果最优,m=min(n,m)

然后可以知道对于a数组进行操作,相对于b也进行了操作,所以只需要保证a,b数组交换后a数组中的数严格减去b数组中的数组。所以可以对a,b数组中的数进行交换。

通过排序之后的数,明显前面的数减去后面的数会出现当前交换的最优解,所以只需要加上即可


#include <bits/stdc++.h>
#define ll long long
using namespace std;
int k,n,m,a[500500],b[500500];
ll res;
int main(){
    cin>>n>>m;
    m=min(n,m);//最少的交换次数
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(a[i]>b[i])swap(a[i],b[i]);
        res+=b[i]-a[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=m;i++){
        k=a[n+1-i]-b[i];
        if(k>0)res+=k*2;
    }
    cout<<res<<endl;
}

上一篇:Easy2d 文档教程之Game类与Window类


下一篇:Java笔记-Java中备忘录模式