题解 CF1043A 【Elections】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 1.9k | 阅读时长 ≈ 2 分钟

一看数据范围， $1 \le n \le 100 $，此时不枚举更待何时？（雾）

注意获胜是指小$A$的票数大于小$B$的票数，而不是大于等于。（原谅作者语文不好$qwq$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110];
int sum1,sum2;
bool comp(int a,int b)//自定义排序函数，从大到小排
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum1+=a[i];//预处理小B的票数
	sort(a+1,a+n+1,comp);//因为k>=max{ai}，所以考虑先排序
	for(int k=a[1];;k++)
	{
		sum2=0;//一定要初始化！
		for(int i=1;i<=n;i++)
		  sum2+=k-a[i];//每个人投给小A的票数就是每个人可以投的票数减去每个人投给小B的票数
		if(sum2>sum1)//是>不是>=
		{
			cout<<k;
			return 0;
		}
	}
	return 0;
}

观察一下代码，我们发现可以在求小$A$的票数部分做一些小小的优化

观察可以发现，$sum2$=$\sum_{i=1}^{n}(k-a_{i})$

原式

$=$ $k\times n-\sum_{i=1}^{n}a_{i}$

$=$ $k\times n-sum1$

于是在求小$A$的票数部分可以优化到$O(1)$复杂度

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110];
int sum1,sum2;
bool comp(int a,int b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum1+=a[i];
	sort(a+1,a+n+1,comp);
	for(int k=a[1];;k++)
	{
		sum2=k*n-sum1;//求小A的票数，当然你也可以不用再设一个变量直接比较
		if(sum2>sum1)
		{
			cout<<k;
			return 0;
		}
	}
	return 0;
}

接下来我们再观察一下这个程序，我们发现，这个程序其实就要求最小的$k$，使得$k$满足$k\times n-sum1>sum1$

这不就是一个不等式吗

移项： $k\times n>2\times sum1$

系数化一: $k>2\times sum1 /n$

于是在求答案的部分就可以优化到$O(1)$复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n;
int a[110];
int sum1;
bool comp(int a,int b)
{
	return a>b;
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum1+=a[i];
	sort(a+1,a+n+1,comp);
	if(2*sum1/n+1<a[1]) cout<<a[1];//因为k要>=max a[i]，所以如果2*sum/n+1<a[1]要输出a[1]
	else cout<<2*sum1/n+1;
	return 0;
}