题解 CF1296E2 【String Coloring (hard version)】

题解- CF1296E2

• 题目意思

  就是要给每个位置分配一种颜色，使得不同的颜色相邻的字符可以完成交换位置。求一种合理的方案。

• 

  思维题。
  其实发现几个显然的性质就很容易啦。

  对于一段相同或者递增的串只要使得他们相同即可，因为不需要进行交换，可以随意填色。但是值得注意的是，如果一个串长成此时就要保证的颜色要不同于因为要使得交换上来。所以对于这次要填的颜色只要暴力找出比它大的最大值即可，复杂度。

• 

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;

int n,m,ans[N],ton[105],tot=1,mx;
int main()
{
    scanf("%d",&n);
    for ( int i=1;i<=n;i++ ) 
    {
        char c;
        cin>>c;
        mx=0;
        for ( int j=(c-'a'+2);j<=26;j++ ) mx=max(mx,ton[j]);
        ans[i]=mx+1;
        ton[c-'a'+1]=max(ton[c-'a'+1],mx+1);
        tot=max(tot,ans[i]);
    }
    printf("%d\n",tot); 
    for ( int i=1;i<=n;i++ ) printf("%d ",ans[i]);
    return 0;
}