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;
}