C. Minimum Notation #823 div2
Problem - C - Codeforces
要反思了,这题我为什么写不对...
没想清楚就开始直接写,导致我的整个思路就是一个很混沌的状态,怎么可能写的对
要改,下次把思路捋清楚再写题
这题的本质是什么
是把前面大的数删掉并且加1插入到随意的一个位置
因为最后的结果必然是升序的,可以把数分为两类
第一类:不删的
第二类删了之后加1的
具体怎么分类,如何分类。(偷队友的一个思路嘻嘻嘻,他实现的好牛逼)
从后面开始枚举,最后一个数必然不动,所以直接划归到第一类
然后开始相邻的数开始比较,如果前面的数小于等于后面的数,这个前面的数可以不变直接加入map
如果前面的数大于后面的数,这个前面的数需要删掉+1,存入map,然后把后面的数(小的数,因为根据这个操作,必然保证了已经操作过的序列是递增的),移到前面来,再继续比较(移动就是赋值的操作)
然后具体的实现看代码吧
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5005,INF=1e18,mod=1e9+7;
map<int,int> mp;
signed main(){
//IOS;
int T;
//T=1;
cin>>T;
while(T--)
{
mp.clear();//存储结果
string ch;
cin>>ch;
if(ch.size()==1)
{
cout<<ch<<"\n";
continue;
}
else
{
mp[ch.back()]++;//最后一个必然不会更改,要么向前移,不可能改的,先加进来
for(int i=ch.size()-2;i>=0;i--)
{
if(ch[i]<=ch[i+1])//然后如果前面的小于后面的,直接加进来就好,然后依次比较
mp[ch[i]]++;
else
{
int now=min((int)ch[i]+1,(int)'9');//如果前面的大说明要删掉,删掉的前提是还要再加1
ch[i]=ch[i+1];//小的向前移
mp[now]++;
}
}
}
for(auto it:mp)//最后的序列必然是升序
{
int x=it.second;
for(int i=1;i<=x;i++) cout<<(char)it.first;
}
cout<<"\n";
}
return 0;
}
/*
尽量让小的移动到前面
大的存起来,放后面
小的移动到去前面
和大的进行判断
*/