C. Lexicographically Largest - 思维

本文主要是介绍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();}
}

这篇关于C. Lexicographically Largest - 思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---