P9661题解

_Kimi_ · 2024-09-29 17:18:17 · 题解

P9661题解

前言

这翻译的什么东西

题意

给一个有 n 个点的完全图，每个点有一个点值。每次进行一次操作，操作是这样的：如果一个点的点权大于与它相连的边数，就另权值减去与它相连的边数，并给与它相连的点点权加一。

如果此操作能不断进行下去，输出 Recurrent，否则按操作完的序列输出。

思路

对于 i\in \left \{ 1, 2, \dots n \right \} 有 A[i] \ge i - 1 就有循环，但是会有极端数据出现，如样例二，所以先把大于 n - 1 的减掉，加回去，排序，特判就没问题了。

操作用优先队列来模拟就好了，比较简单，看代码理解理解就好。

代码

//code by Kimi
#include<bits/stdc++.h>
#define int long long
#define sept fixed << setprecision(4)
#define debug(x) cerr << (#x) << endl
#define pb emplace_back
#define endl '\n'
#define WA AC
using namespace std;
const int maxn = 5e5 + 10;
int n, v;
int A[maxn], B[maxn], ans[maxn];
priority_queue<pair<int, int> > q;
void check(){
    int tmp;
    for(int i = 1; i <= n; i++) B[i] = A[i];
    for(int i = 1; i <= n; i++){
        tmp = B[i] / (n - 1);
        v += tmp;
        B[i] %= (n - 1), B[i] -= tmp;
    }
    for(int i = 1; i <= n; i++) B[i] += v;
    sort(B + 1, B + n + 1);
    for(int i = 1; i <= n; i++){
        if(B[i] < i - 1) return;
    }
    cout << "Recurrent" << endl;
    exit(0);
}
void input(){
    srand(19491001);
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> A[i];
    check();
    v = 0;
}
void init(){}
signed main(){
    init();
    input();
    for(int i = 1; i <= n; i++) q.push({A[i], i});
    while(q.top().first + v >= n - 1){
        int top1 = q.top().first, top2 = q.top().second;
        q.pop();
        top1 += v, top1 -= (n - 1), v++;
        q.push({top1 - v, top2});
    }
    while(q.size()){
        auto top = q.top();
        q.pop();
        ans[top.second] = top.first + v;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}