C. Lexicographically Largest - 思维

题面

分析

如果没有相同的数那么一定是从最后一个开始向前一个个放入集合，这样不会损失，一旦有相同的，从右向左依次放入，那么一旦遇到集合里已经有的元素，此时最优策略就是将当前这个数减一再放进去，那么此时我可以将他前面的那个数先放进去，然后在放这个数，呢么简单来做也就是将数组按照从大到小排序，如果遇到相邻相同元素，那么就可以将后面这个元素减一，同时需要维护保证数组始终单调递减。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i ++) {
        cin >> a[i];
        a[i] += i + 1;
    }
    sort(a.begin(), a.end(), greater<ll>());
    for(int i = 1; i < n ;i ++) {
        if(a[i] > a[i - 1]) a[i] = a[i - 1] - 1;
        if(a[i] == a[i - 1]) a[i] --;
    }
    for(int i = 0; i < n; i ++) cout << a[i] << ' ';
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}