题意：a和b都代表字符串的下标，至少用k个字符，构造一个长度为n的字符串，将这个字符串中的字符按无论是按$a$写还是按$b$写，字典序都非递减。
思路：如果将$a[l,r]=b[l,r]$，相等的意思是字符重排列后相等。那显然这个一段区间可以用相同的字符来写，我们贪心的将1-n这样的相等的团全部划分出来，团的数量即我最多能用多少字符，小于k则输出-1，超出26的部分用‘z’代替即可。
#pragma GCC optimize (2) #pragma G++ optimize (2) #pragma comment(linker, "/STACK:102400000,102400000") #include<bits/stdc++.h> #include<cstdio> #include<vector> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,b,a) for(int i=b;i>=a;i--) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; const int maxn=200010; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int vis1[maxn],vis2[maxn],a[maxn],b[maxn]; int n,k,tot,sa,sb,sta[maxn]; int ans[maxn]; int main(){ cin>>n>>k; rep(i,1,n) { scanf("%d",&a[i]); } int num=0; int top=0; rep(i,1,n) { scanf("%d",&b[i]); vis2[a[i]]?(vis2[a[i]]=0,num--):(vis1[a[i]]=1,num++,sta[++top]=a[i]); vis1[b[i]]?(vis1[b[i]]=0,num--):(vis2[b[i]]=1,num++,sta[++top]=b[i]); if(num==0){ ++tot; while(top){ ans[sta[top--]]=tot; } } } if(tot<k)puts("NO"); else{ int cnt=1; puts("YES"); for(int i=1;i<=n;i++){ printf("%c",‘a‘+min(ans[i]-1,k-1)); } } }
codeforces1213F Unstable String Sort 思维
原文：https://www.cnblogs.com/mountaink/p/11599380.html