[ABC329D] Election Quick Report 题解

题目翻译

有一场选举，要从 \(N\) 名候选人中选出一名获胜者，候选人编号为 \(1, 2, \ldots, N\)，共有 \(M\) 张选票。

每张选票正好投给一位候选人，其中 \(i\) 票投给了候选人 \(A_i\)。

选票将按照从第一张到最后一张的顺序进行统计，每张选票统计完毕后，将更新并显示当前的获胜者。

得票最多的候选人即为获胜者。如果有多个候选人得票最多，则候选人编号最小者为获胜者。

对于每个 \(i = 1, 2, \ldots, M\)，如果只计算前 \(i\) 张选票，则确定获胜者。

分析

每次操作我们只需要对之前的最大值进行比较，如果比他还大，那么更新最大值。因为我们要知道是哪一个人的，所以用一个 pair 来存储其对应的下标。

比较方式是如果大于，则替换；如果等于且下标小于（小于等于），也替换。

AC code：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define se second
#define endl '\n'
#define debug puts("AK IOI")
using namespace std;
const int N = 2e5+5;
int a[N];
int n,m;
pair<int,int> maxn;
int vis[N];
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		scanf("%d",&a[i]);
		vis[a[i]]++;
		if(vis[a[i]] > maxn.first || (vis[a[i]]==maxn.first && a[i] < maxn.second)){
			maxn.first = vis[a[i]];
			maxn.second = a[i];
		}cout<<maxn.second<<endl;
	}
	return 0;
}