Codeforces Round #577 (Div.2) 题解

A - Important Exam

题意：有 n n n位考生参加一场有 m m m道题的考试，给出它们的作答情况（每道题只可能有A,B,C,D,E五个选项）和每道题的分值，问在最好情况下，它们的总分最多为多少。

思路：暴力枚举，统计每道题每个选项的人数。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1005],cnt[1005][6],ans=0;
char s[1005][1005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>s[i][j];
			cnt[j][s[i][j]-'A']++;
		}
	}
	for(int i=1;i<=m;i++)	cin>>a[i];
	for(int i=1;i<=m;i++){
		int mx=0;
		for(int j=0;j<5;j++)	mx=max(mx,cnt[i][j]);
		ans+=a[i]*mx;
	}
	cout<<ans<<endl;
	return 0;
}
           

B - Zero Array

题意：给你一个长度为 n n n的数组，每次你可以选择任意两个不同位置上的数并将它们减 1 1 1，问能否经过有限次操作将该数组中每一个元素都变为 0 0 0。

思路：该数组能经过有限次操作将每一个元素都变为 0 0 0当且仅当：

1. 数组中所有元素的和为偶数。
2. 数组中从小到大排列的前 n − 1 n-1 n−1个数的和大于等于第 n n n个数。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100005],sum,sum0,zero=0;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++)	sum+=a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++)	sum0+=a[i];
	if(sum0<a[n])		puts("NO");
	else if(sum%2==0)	puts("YES");
	else				puts("NO");
	return 0;
}
           

C - Maximum Array

题意：有一个长度为 n n n（ n n n是奇数）的 a a a数组，你最多可以进行 k k k次操作，每次你可以将数组中任意一个元素的值 + 1 +1 +1，问最终得到的数组的中位数最大是多少。

思路：我们将数组排个序，那么中位数就是 a [ ( n + 1 ) / 2 ] a[(n+1)/2] a[(n+1)/2]，考虑先将中位数不断加 1 1 1，直到它与 a [ ( n + 1 ) / 2 + 1 ] a[(n+1)/2+1] a[(n+1)/2+1]相等，然后再将这两个数同时加 1 1 1，直到它们与 a [ ( n + 1 ) / 2 + 2 ] a[(n+1)/2+2] a[(n+1)/2+2]相等，一次类推，直到操作数量等于 k k k为止。

C o d e : Code: Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[200005],n,k,ans;
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)	cin>>a[i];
	if(n==1)	return cout<<(int)a[1]+k<<endl,0;
	sort(a+1,a+n+1);
	int mid=(n+1)/2,cur=mid,sum=0;
	ans=a[mid];
	while(k){
		if(cur==n){
			ans+=k/(n-mid+1);
			break;
		}
		if(a[cur+1]!=a[cur]){
			int next=k-(cur-mid+1)*(a[cur+1]-a[cur]);
			if(next<0){
				ans+=k/(cur-mid+1);
				break;
			}
			else	k=next;
		}
		cur++;
		ans=a[cur];
	}
	cout<<ans<<endl;
	return 0;
}