本文主要是介绍CodeForces 425A Sereja and Swaps,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
一串数字 最多可以做k次交换数字 求 最大连续和是多少
思路:
n^2暴力枚举所有区间 那么如果要换数字 一定是从区间外拿大数换区间内的小数 优先队列可以完成操作
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define N 201int n,m,ans;
int a[N];
priority_queue<int> q2;
priority_queue< int , vector<int> , greater<int> > q1;int main()
{int i,j,k,sum,f1,f2;scanf("%d%d",&n,&m);for(i=1,ans=-10000;i<=n;i++){scanf("%d",&a[i]);ans=max(ans,a[i]);}for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();for(k=1,sum=0;k<=n;k++){if(k<i||k>j) q2.push(a[k]);else{q1.push(a[k]);sum+=a[k];}}for(k=m;k&&!q1.empty()&&!q2.empty();k--){f1=q1.top();q1.pop();f2=q2.top();q2.pop();if(f1<f2){sum-=f1;sum+=f2;}else break;}ans=max(ans,sum);//printf("%d %d %d %d\n",i,j,sum,ans);}}printf("%d\n",ans);return 0;
}
这篇关于CodeForces 425A Sereja and Swaps的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!