本文主要是介绍2021.7.30 Codeforces Round #723 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A
分析题意
给一个数组，求该数组的一个排列，满足每一项不等于相邻两项的平均值。
Example
inputCopy
3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9
outputCopy
3 1 4 2 5 6
123 10 456 789
9 6
Note
In the first testcase, array [3,1,4,2,5,6] works, as it’s a permutation of [1,2,3,4,5,6], and 3+42≠1, 1+22≠4, 4+52≠2, 2+62≠5, 5+32≠6, 6+12≠3.
314256
142563
425631
256314
563142
631425
314256
由于是一个环形，所以怎么样都ok
如果再大一点就可以发现规律了
123456789
-》
1_2_3_4_5
_6_7_8_9
发现是不是这样就可以啦？
因为对任意一个数字来说，大于它的两个数字的算术平均数也一定大于ta
所以排序交替输出就好了
#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[100010];
vector<int>ji;
vector<int>ou;
int main(){cin>>T;while(T--){cin>>n;for(int i=1;i<=2*n;i++)cin>>a[i];sort(a+1,a+1+2*n);int i=1;int j=n+1;for(int k=1;k<=2*n;k++){if(k&1){cout<<a[i]<<" ";i++;}else {cout<<a[j]<<" ";j++;}}cout<<endl;}
}
b题
以下都是错误的code
#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[18];
int main(){cin>>T;while(T--){cin>>n;n%=111;n%=11;if(n==0)puts("YES");else puts("NO");}
}#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[18];
int main(){cin>>T;while(T--){cin>>n;int x=n%11;int b=n-11*x;int a=x-10*b;if(x!=11*a+111*b)puts("YES");else puts("NO");}
}
Accepted
#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[18];string solve(int n){int b=n%11;n-=111*b;if(n<0)return "NO";n%=11;if(n==0)return "YES";else return "NO";
}int main(){cin>>T;while(T--){cin>>n;cout<<solve(n)<<endl;}
}
C1
This is the easy version of the problem. The only difference is that in this version n≤2000. You can make hacks only if both versions of the problem are solved.
There are n potions in a line, with potion 1 on the far left and potion n on the far right. Each potion will increase your health by ai when drunk. ai can be negative, meaning that potion will decrease will health.
You start with 0 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
What is the largest number of potions you can drink?
Input
The first line contains a single integer n (1≤n≤2000) — the number of potions.
The next line contains n integers a1, a2, … ,an (−109≤ai≤109) which represent the change in health after drinking that potion.
Output
Output a single integer, the maximum number of potions you can drink without your health becoming negative.
Example
inputCopy
6
4 -4 1 -3 1 -3
outputCopy
5
Note
For the sample, you can drink 5 potions by taking potions 1, 3, 4, 5 and 6. It is not possible to drink all 6 potions because your health will go negative at some point
看完题目，很明显是线性动态规划。
动态规划问题，首先要找到变化的状态有哪些。
这题的变化态有3个：
遇到的药水数，喝了的瓶数，生命值。
在整个过程中，只有上面三个量在变化。
然后我们注意到，题目要我们求在生命值不为负数的情况下最多能喝多少瓶。
设dp[i][j]表示前i瓶中喝j瓶能剩下的最大生命值，
那么状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i])
将初始值设为无穷小，dp[0]=0，再用滚动数组降维。
最后从后往前，dp[i]>=0的最大i值就是答案。
这个用滚动数组压缩到二维的没有过
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[20010];
int dp[2][20010];//表示前i瓶药水喝了j瓶药水时的最大健康值
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];memset(dp,-0x3f,sizeof dp);dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=i;j>=1;j--){if(dp[(i-1)%2][j-1]+a[i]>=0)dp[i%2][j]=max(dp[(i-1)%2][j] , dp[(i-1)%2][j-1]+a[i]);else dp[i%2][j]=dp[(i-1)%2][j];}}for(int i=n;i>=1;i--){if(dp[n%2][i]>=0){cout<<i;return 0;}}}
这个直接压缩到一维的过掉了
#include<iostream>
#include<algorithm>
#define ll long long int
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
ll a[200005];
ll dp[200005];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) dp[i]=-INF;dp[0]=0;for(int i=1;i<=n;i++){for(int j=i;j>0;j--){if(dp[j-1]+a[i]>=0){dp[j]=max(dp[j],dp[j-1]+a[i]);}}}for(int i=n;i>=0;i--){if(dp[i]>=0){cout<<i<<endl;return 0;}}
}hard version把n扩大到20万了
不能用dp做
我们考虑贪心，使用优先队列大顶堆+反悔
#include<iostream>
#include<queue>
#define ll long long int
using namespace std;
priority_queue<ll> q;//大根堆
int main()
{int n;cin>>n;ll s=0;ll ans=0;ll x;for(int i=0;i<n;i++){cin>>x;if(x>=0){s+=x;ans++;}else if(s+x>=0){s+=x;q.push(-x);ans++;}else if(!q.empty()){if(-x<q.top()){s+=x+q.top();q.pop();q.push(-x);}} }cout<<ans<<endl;return 0;
}else if(!heap.empty()){int t=heap.top();if(-x<t)heap.pop(),heap.push(-x),xue+=t+x;}
这道题有点像勇者斗恶龙
好好吸收好好消化
这道题真的很好
谢谢这个博主，谢谢它的整理，真的学到很多
这篇关于2021.7.30 Codeforces Round #723 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
