Codeforces Round 953 (Div. 2)（A~D题解）

这次比赛是我最顺利的一次比赛，也是成功在中途打进前1500，写完第三道题的时候也是保持在1600左右，但是后面就啥都不会了，还吃了点罚时，虽说如此也算是看到进步了，D题学长说很简单，但是我当时分析错了，出了一点小问题，不然最后也能定格在2000左右，下次加油。

A. Alice and Books

 

题意：就是说给你n本书，让你从中间分开，阅读边编号最大的那本书，然后问你最多能读多少页，这个很简单，最后一本书肯定是要读的，我们只需要遍历从1到~n-1本书，找到那本书页数最多然后加起来就OK了

#include<bits/stdc++.h>
using namespace std;
#define int long longint t;
int n;
int a[105];
int maxn=0;
signed main()
{cin>>t;while(t--){maxn=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){maxn=max(maxn,a[i]);}cout<<maxn+a[n]<<"\n";}return 0;
}

 B. New Bakery

 

题意：就是说给你n个面包，每个面包有两种卖价，一个是a元，一个是b元，b元的计算是

（b-i+1）也就是说越往后卖b价越低

思路：既然b价格越来越低，那么等b的价格和a一样的时候就按a的价格卖即可，因此我们一开始做出判断如果a>b那就全按a的价格来卖，如果a<b，那么等b的价格低到和a一样的时候就按a元来卖就有最大价值

ps：同时要注意 b是否真的会低到a的价格

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a,b;
signed main()
{cin>>t;while(t--){cin>>n>>a>>b;if(a>=b){cout<<a*n<<"\n";}else{int sum=0;int flag=b-a;if(n>flag){sum=(a+1+b)*(b-a)/2+(n-flag)*a;}else{sum=(b+b-n+1)*n/2;}cout<<sum<<"\n";}}return 0;
}

 C. Manhattan Permutations

 

题意：就是给你一个数组，数组的数值是1~n，然后问你其中产生的曼哈顿值是否能达到k

思路：我们首先要判断哪些情况下不会达到，首先就是因为你是交换产生的曼哈顿值，曼哈顿值一但产生就必然是偶数，而不可能是奇数，当k为奇数时直接输出NO即可

其次就是当整个序列反转的时候产生最大的曼哈顿值，因而假如我们的k要是大于反转之后的曼哈顿值也要输出NO

然后就是很简单的根据k去进行翻转就好，我们要对k的值进行判断，我们要从第一个数开始交换，然后每次交换都是要根据k值的大小去交换的（这个地方不会的直接私我吧，文学功底有限，实在太难纯文本将清楚了）

#include<bits/stdc++.h>
using namespace std;
#define int long longint t;
int n,k;
int maxn;//用于计算最大差值 
int a[200005];
signed main()
{cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++)a[i]=i;if(k%2!=0){cout<<"NO\n";continue;}maxn = 0; for(int i=1;i<=n;i++){maxn+=abs(n-i+1-i);}if(maxn<k){cout<<"NO\n";continue;}int flag=2*(n-1);int num=1;while(k!=0){if(k>=flag){
//            	cout<<flag<<"\n";
//            	cout<<a[num]<<" "<<a[n-num+1]<<"flag\n";int t=a[num];a[num]=a[n-num+1];a[n-num+1]=t;k-=flag;num++;flag=2*(n-num+1-num);}else{int cnt=k/2;int t=a[num];a[num]=a[num+cnt];a[num+cnt]=t;k=0;}}cout<<"YES\n";for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<"\n";}return 0;
}

D. Elections 

 

题意：就是说有n个候选人，c个无主见人士，无主见的人会将票投给下标最小的那个的人，然后问你想要让第i个当选，要排除最少多少个竞争者

 思路：我们需要去对于

（1）第一个要特判，如果第一个加上未决定的票数就可以大于最多的，那么第一个人不用将任何候选人排除

（2）如果我票数就是最多的且我的下标小的话也可以在同票数的情况下获胜，并且第一个人+c个人的票也无法超过我，因此，也不需要排除别人

 （3）其余的需要判断其是否比最大值那个下标小，或者说把前面的都筛掉之后+c能否大于最多那个人得票数，如果这两个条件满足其一，就输出i-1即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,c;
int a[200005];
int pre[200005];
bool cmp(pair<int,int> a, pair<int,int> b)
{if(a.first==b.first) return a.second>b.second;return a.first<b.first;
}
void solve()
{cin >> n >> c;vector<pair<int,int>> b(n+1);b[0]={0,0};for(int i=1;i<=n;i++){cin >> a[i];b[i]={a[i],i};}sort(b.begin(),b.end(), cmp);for(int i=1;i<=n;i++){pre[i]=pre[i-1]+b[i].first;}int sum=0;for(int i=1;i<=n;i++){if(i==1 && a[i]+c>=b[n].first){cout << 0 << ' '; }else if(((a[i]==b[n].first && i<=b[n].second)) && a[1]+c<a[i]){cout << 0 << ' ';}else{cout << i-(b[n].second<=i || sum+a[i]+c>=b[n].first)<<' ';}sum+=a[i];}cout << "\n";
}
signed main()
{cin >> t;while(t--){solve();}return 0;
}