2019-2020 ICPC, NERC, Northern Eurasia Finals E. Elections (暴力&贪心)

题意：给定$n$个候选人，$m$个站点，第$n$个人是反对候选人，每个站点会有$n$个人投票个数。

要求删除最少的站使得第$n$个人的总票数不是严格最多的那个人。

思路：暴力$+$贪心。

我们的目的是使第$n$个人不是严格最多的，那么我们就可以假设最后最多的那个人是$goal$，然后我们可以暴力枚举$goal$对应要删除的站数，然后取最小的即可。

有了$goal$我们就很好贪心的删了，我们取所有站的这两个人票数差，然后由大到小取，直到$cn{t}_{goal}\ge cn{t}_n$即可。

时间复杂度：$O(nmlogm)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int n,m;
int a[N][N],sum[N],tmp[N],mn=1e9;
vector<int>ans,res;
struct cha{
	int id;
	int x;
	bool operator<(const cha&c)const{
		return x>c.x; 
	}
}C[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			sum[j]+=a[i][j];
		}
	}
	for(int i=1;i<=n;i++) tmp[i]=sum[i];
	sort(tmp+1,tmp+n+1);
	if(tmp[n]!=sum[n]||(tmp[n-1]==tmp[n])){
		puts("0");
		puts("");
		return 0;
	} 
	for(int goal=1;goal<n;goal++){
		int sg=sum[goal],sn=sum[n];
		sn-=sg;
		ans.clear();
		for(int i=1;i<=m;i++){
			C[i].x=a[i][n]-a[i][goal];
			C[i].id=i;
		}
		sort(C+1,C+m+1);
		int cnt=0; 
		for(int i=1;C[i].x>0&&i<=m;i++){
			sn-=C[i].x;
			cnt++,ans.pb(C[i].id);
			if(sn<=0) break; 
		}
		if(sn<=0){
		//	printf("goal=%d\n",goal);
			if(ans.size()<mn){
 
				res=ans;
				mn=ans.size();
			}
		}
	}
	printf("%d\n",mn);
	for(int i:res) printf("%d ",i);
	return 0;
}

---

总结：这种题给了我们一个思考问题的新方向，对于一个问题，我们可以假设答案的结果，然后取依次暴力选取。