题解：AT_abc483_c [ABC483C] Second Choice Election

Self_Silent · 2026-11-10 19:58:51 · 题解

题意

有 n 名候选人和 m 名选民，每位选民有第一志愿和第二志愿，得票最多者当选。
对于每一位候选人 k，假设只有他退选，原本投给他的选民将改投第二志愿，其余选民投票不变。
最后输出每一位候选人退选时，最终的当选者。

思路

每次都暴力从头模拟肯定会超时，所以我们要想一个高效的方法。

仔细观察后可以发现：当候选人 k 退选时，只有原本第一志愿投给 k 的那部分选民的票会发生转移，其他选民的投票意向不变。

那我们可以这样：

先计算出无人退选时，所有候选人的得票数；
对于每个候选人 k，我们只需要把投给 k 的票“挪走”，加到对应的第二志愿候选人身上，观察新的票数分布，找出最高票即可。处理完后再“撤销”这些改动，以便处理下一个 k。

这样，每张选票在整个过程中只会被处理常数次。

此外，我们并不需要每次都检查所有候选人的票数。因为当选者只可能是以下几种情况：

原本无人退选时的第一名或第二名（如果第一名退选，第二名可能递补；如果其他人退选，前两名票数不变或略减，仍最有可能当选）；
或者是因为 k 退选而获得了额外选票的那些候选人（也就是 k 的选民的第二志愿）。

所以，我们每次只需要检查少数候选人的票数，就可以确定新的当选者。

具体实现

定义。记录当前票数，邻接表记录谁把第二志愿投给了谁，收集可能当选的候选人。

int n,m,a[N],b[N],c[N],d[N],k[N],kc;
vector<int> v[N];
// c：记录票数，v：谁给谁投了票，k：可能成为最高票的候选人

排序。按照优先票数，后编号的方式排序。用于找出最初的前两名。

bool cmp(int u,int w){
  if(c[u]!=c[w]) return c[u]>c[w];//票数
  return u<w;//编号
}

具体实现操作：

找出无人退选时的前两名。对所有人排一次序，记录下前两名，作为后续比较的保底候选人。
```
for(int i=1;i<=n;i++) d[i]=i;
sort(d+1,d+n+1,cmp);
int top1=d[1],top2=(n>=2?d[2]:0);
```
依次模拟每个候选人退选。将候选人 i 的票清零，并通过邻接表 v 把他的票加给对应的第二志愿。
```
for(int i=1;i<=n;i++){
    c[i]=0;//撤销i的票
    for(int x:v[i]) c[x]++;//票转给第二志愿
}
```
收集关键候选人。将初始前两名，以及所有获得转移票的人，统统放进 k 数组（无需去重，不影响求最大值）。
```
  kc=0;
  k[kc++]=top1;
  if(top2) k[kc++]=top2;
  for(int to:v[i]) k[kc++]=to;
```

在关键候选人中找最高票。遍历 k 数组，比较票数，票数相同比编号，选出最终当选者。

  int w=0;
  for(int j=0;j<kc;j++){
      int t=k[j];
      if(!w||c[t]>c[w]||(c[t]==c[w]&&t<w)) w=t;
  }
  cout<<w<<"\n";

最后复原状态。把刚才加给别人的票减掉，恢复原本的票数，保证下一轮循环时票数状态是最初的。
```
  for(int to:v[i]) c[to]--;//减回转移的票
  c[i]=v[i].size(); //恢复i的票数
```

代码

细节已在上面讲明（个人认为），此处不过多赘述。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],b[N],c[N],d[N],k[N],kc;
vector<int> v[N];
bool cmp(int u,int w){
    if(c[u]!=c[w]) return c[u]>c[w];
    return u<w;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        c[a[i]]++;
        v[a[i]].push_back(b[i]);
    }
    for(int i=1;i<=n;i++) d[i]=i;
    sort(d+1,d+n+1,cmp);
    int top1=d[1],top2=(n>=2?d[2]:0);
    for(int i=1;i<=n;i++){
        c[i]=0;
        for(int x:v[i]) c[x]++;
        kc=0;
        k[kc++]=top1;
        if(top2) k[kc++]=top2;
        for(int to:v[i]) k[kc++]=to;
        int w=0;
        for(int j=0;j<kc;j++){
            int t=k[j];
            if(!w) w=t;
            else if(c[t]>c[w]||(c[t]==c[w]&&t<w)) w=t;
        }
        cout<<w<<"\n";
        for(int to:v[i]) c[to]--;
        c[i]=v[i].size();
    }
    return 0;
}

记录（我加了一点注释）