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

本文主要是介绍Codeforces Round 953 (Div. 2) （A~D），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round 953 (Div. 2)

写在前面

今天挑了一场div2来打，感觉这场div2的难度比暑假div2的难度低很多，A~D这四道题的考点都是模拟和贪心，把玩一下就能写出来，总体来说难度不大 QAQ

A. Alice and Books

思路

签到题，由于Alice选的是这两堆中编号最大的下标，那么编号为n的下标它一定会选
根据贪心策略，我们只需要在1~n-1中选择最大的页数,然后加上编号为n的页数即可

code

int a[N];
void solve(){int n;cin >> n;int mx=0,k=0;for(int i=1;i<=n;++i){cin >> a[i];	if(a[i]>mx) mx=a[i],k=i;}if(k==n){int maxn=0;for(int i=1;i<n;++i) maxn=max(maxn,a[i]);cout << mx+maxn << endl;}else{cout << mx+a[n] << endl;}return ;
}

B. New Bakery

思路

根据贪心策略，每个馒头的价钱都让它们尽可能大，那么这题就有3种情况：

• 先比较a和b的大小，如果a比b大，那么全部都按a的价钱来算
• 先按b的价钱来算，如果全部都按b的价钱来算且最后一个馒头的价钱大于等于a，那就全按b的价钱来算
• 反之，根据不等式$a=b-i+1$ ,即 $i=b-a+1$ ,那就是 $[1,i]$ 按b的价钱来算，$[i+1,n]$ 按a的价钱来算

code

void solve(){int n,a,b;cin >> n >> a >> b;if(a>=b){cout << a*n << endl;return ;}int k=b-a+1;if(k>=n){a=b-n+1;cout << (a+b)*n/2 << endl;return ;}cout << (a+b)*k/2+(n-k)*a << endl;return ;
}

C. Manhattan Permutations

思路

把玩一下不难发现，无论怎么交换，一个序列的曼哈顿值一定为偶数（很好证明，这里就不证了）

根据贪心策略，我们将第一个数和最后一个数换位，将第二个数和倒数第二个数换位········
这样可以得到它最大的曼哈顿值，如果k大于这个值，那就一定不满足题意
反之，它就一定满足题意，我们可以用两个指针去维护 $[1,n]$ 这个区间

我们交换任意两个数，它的价值都是 $2\ast |x-1|$ $x$为这两个数中最大的数
因此我们只需要凑 $k/2$ 的价值，维护右指针 $min(x,n-1-2\ast i)$ 即可

具体实现看代码~~

code

int a[N];
void solve(){int n,k;cin >> n >> k;int sum=0;int p=n;for(int i=1;i<=n/2;++i) sum+=2*(p-i),p--;if(k & 1 || k>sum){cout << "NO" << endl;return ;}for(int i=1;i<=n;++i) a[i]=i;int x=k/2;for(int i=1,j=min(x,n-1);;++i){swap(a[i],a[i+j]);x-=j;j=min(x,n-1-2*i);if(x==0) break;}cout << "YES" << endl;for(int i=1;i<=n;++i) cout << a[i] << " ";cout << endl;return ;
}

D. Elections

思路

把玩一下不难发现，如果当前状态 $a_i$ 不为序列中最大的数，那么它就必须将它前面所有的候选人都排除

由于 “举棋不定者” 只会将票数投给当前序列中下标最小的候选人
只有将 $i$ 前面的人都排除， $a_i$ 这个候选人才能受到支持

这时需要进行判断：

• 排除完前面的候选人，它的票数仍然比最高票数的候选人少，那就必须将最高票数的候选人排除，即排除 $i$ 个人
• 反之只需要排除前面 $i-1$个人即可

具体代码很简单，感觉这题作为div2的D题偏简单了

code

const int N=1e6+5;
int a[N],sum[N];
void solve(){int n,c;cin >> n >> c;int maxn=-1;int k=0;for(int i=1;i<=n;++i){cin >> a[i];if(i==1) a[i]+=c;sum[i]=sum[i-1]+a[i];if(maxn<a[i]){maxn=a[i];k=i;}} for(int i=1;i<=n;++i){if(i==k) cout << 0 << " ";else{if(sum[i]>=maxn) cout << i-1 << " ";else cout << i << " ";}}cout << endl;return ;
}

这篇关于Codeforces Round 953 (Div. 2) （A~D）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---