题解：AT_abc483_c [ABC483C] Second Choice Election

No_water · 2026-11-10 23:04:32 · 题解

分享一下我的思路：

先用向量存每一个人弃选后，所有能得到他的票的所有人。和他的原本有的票数。

预处理最大值和最大值出现的下标。

枚举第 i 人弃选。

这一人原本是最大值，重算一遍。注意，我们的循环有的最大值只有一个，所以只操作一遍，不会超时。

然后都是增加其他能多得票的人。

最后输出加还原，不要干扰后面的循环。

上述求最大值还要取下标小的，我忽略不说了，具体在代码。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n;
int m;
int maxa;
int id;
int a[N];
int b[N];
int s[N];
int s1[N];
vector<int> g[N];
signed main(){
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> a[i] >> b[i];
        s1[a[i]]++;
        g[a[i]].push_back(b[i]);
    }
    for(int i = 1; i <= n; i ++){
        if(s1[i] > maxa){
            maxa = s1[i];
            id = i;
        }
        s[i] = s1[i];//存一下
        // cout << s1[i] << " " << s2[i] << endl;
    }
    for(int i = 1; i <= n; i ++){
        //第i个人不选
        int oldid = id;
        int oldmax = maxa;
        int old = s[i];
        s[i] = 0;
        int m = g[i].size();
        if(id == i){//重算
            maxa = -1;
            id = -1;
            for(int j = 1; j <= n; j ++){
                if(i == j){
                    continue;
                }
                if(s[j] > maxa){
                    maxa = s[j];
                    id = j;
                }else if(s[j] == maxa && id > j){
                    id = j;
                }
            }
        }
        for(int j = 0; j < m; j ++){
            s[g[i][j]]++;//增加
            if(s[g[i][j]] > maxa){
                maxa = s[g[i][j]];
                id = g[i][j];
            }else if(s[g[i][j]] == maxa && id > g[i][j]){
                id = g[i][j];
            }
        }
        cout << id << endl;
        //还原
        for(int j = 0; j < m; j ++){
            s[g[i][j]]--;
        }
        s[i] = old;
        maxa = oldmax;
        id = oldid;
    }
    return 0;
}