Codeforces Round #577 (Div. 2) 解析

A. Important Exam

题意：有 $n$ 个学生和 $m$ 个问题，给出每个学生的答案和每个问题的分值，求出最可能的所有学生总分。

输入：第一行，$n$ 和 $m$；第 $2\sim n+1$ 行，每行一个字符串，代表每个学生的答案；最后一行 $m$ 个数，代表每个问题的分值。

输出：一个数，最可能的学生总分。

解析：大水题，找到每个问题回答次数最多的那个答案，依次加上次数乘以分值，即可得出答案。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,flag[6];
int p[1010],ans;
char s[1010][1010];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=m;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<=m;i++)
	{
		int maxx=0;
		for(int j=0;j<=5;j++)
			flag[j]=0;
		for(int j=1;j<=n;j++)
			flag[s[j][i]-'A'+1]++;
		for(int j=1;j<=5;j++)
			maxx=max(maxx,flag[j]);
		ans+=maxx*p[i];
	}
	printf("%d",ans);
    return 0;
}

B. Zero Array

题意：给你 $n$ 个数，每次可以选择任意两个数减 $1$，判断最后能否让所有数都为 $0$。

输入：第一行，$n$；第二行 $n$ 个数。

输出：如果能，输出 YES，否则输出 NO。

解析： 两个点，如果 $n$ 个数总和为奇数或最大的数大于其他数总和就不行。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,maxx,sum,x;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		sum+=x;
		maxx=max(maxx,x);
	}
	if(sum&1||maxx*2>sum)
		printf("NO");
	else
		printf("YES");
    return 0;
}

C. Maximum Median

题意：给你 $n$ 个数，保证 $n$ 是奇数。你有 $k$ 次操作，使其中一个数加 $1$。问你 $k$ 次操作后，能达到的中位数最大为多少。

输入：第一行，$n$ 和 $k$；第二行 $n$ 个数。

输出：一个数，能达到的最大中位数。

解析：将 $n$ 个数排序，很明显，对前 $\frac{n}{2}$ 个数操作没有任何作用，所以可以将前 $\frac{n}{2}$ 个数删掉，此时中位数就变成了剩下数列中最小的数，要使最小的数最大，直接二分答案即可。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,k;
long long a[201010];
bool judge(long long x)
{
	long long sum=0;
	for(int i=1;i<=n;i++)
		if(x>a[i])
			sum+=(x-a[i]);
	return sum<=k;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	n=n/2+1;
	for(int i=1;i<=n;i++)
		a[i]=a[n+i-1];
	long long l=1,r=2e9;
	while(l<r)
	{
		long long mid=(l+r+1)/2;
		if(judge(mid))
			l=mid;
		else
			r=mid-1;
	}
	printf("%lld",l);
    return 0;
}