长沙做网站企业,网站备案查询官网,wordpress 外网访问不了,海南做网站公司哪家好更好的阅读体验
C. Minimum Notation
思路#xff1a;我们可以进行的操作时将一个位置的数删除然后在任意位置处添加一个比当前数大1并且小于9的数#xff0c;所以我们的操作只会让一个数变大#xff0c;我们统计一个最大值的后缀#xff0c;贪心的考虑如果当前数的后面有…更好的阅读体验
C. Minimum Notation
思路我们可以进行的操作时将一个位置的数删除然后在任意位置处添加一个比当前数大1并且小于9的数所以我们的操作只会让一个数变大我们统计一个最大值的后缀贪心的考虑如果当前数的后面有比他小的数的话我们就需要让这个小的数往前走才能使字典序变小如果当前值小于 后缀的最小值说明这个数后面的所有数往前移动都不能使字典序变得更小所以我们统计完后缀后从前往后扫一遍用multiset维护以下即可。
#include bits/stdc.husing namespace std;
typedef long long LL;
const int N 1e6 10;
char c[N], suf[N];
void run()
{scanf(%s, c 1);int mn 10;int n strlen(c 1);for(int i n; i 1; -- i){int num c[i] - 0;if(num mn) mn num;suf[i] mn;} multisetints;for(int i 1; i n; i){int num c[i] - 0;if(num suf[i]) s.insert(num);else{if(num 9) s.insert(9);else s.insert(min(num 1, 9));}}for(auto x : s) cout x;printf(\n);
}int main()
{
// freopen(1.in, r, stdin);int t;cin t;while(t --) run(); return 0;
}
