[COCI 2017/2018 #4] Izbori

思路

本来以为挺难的，结果发现数据小的可怜……

第一问开个桶记录一下得票数最多的人即可。

第二问我们可以枚举哪些人弃票，然后用第一轮的方法检查一下主席是不是 $K$ 即可。

代码

时间复杂度 $O(2^{M}NM)$，可过且跑得飞快。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[105][20],t[20];
bool bj[20];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	int max1=0;//记录赢得选举的主席
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cin>>a[i][j];
		t[a[i][1]]++;
		if(t[max1]<t[a[i][1]]||(t[max1]==t[a[i][1]]&&max1>a[i][1])) max1=a[i][1];
	}
	cout<<max1<<"\n";
	int ans=1e9;
	for(int i=0;i<(1<<m);i++)//枚举的是退出选举的人
	{
		memset(bj,0,sizeof(bj));
		memset(t,0,sizeof(t));
		int l=0,max1=0;
		for(int j=0;j<m;j++) if((1<<j)&i) l++,bj[j+1]=1;//统计有多少人退出选举
		if(l>=ans) continue ;//很有用的小优化
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				if(!bj[a[j][k]])
				{
					t[a[j][k]]++;
					if(t[max1]<t[a[j][k]]||(t[max1]==t[a[j][k]]&&max1>a[j][k])) max1=a[j][k];
					break;
				}
		if(max1==k) ans=min(ans,l);
	}
	cout<<ans;
	return 0;
}