CF1213F Unstable String Sort

题目链接

问题分析

题目实际上是一堆大于等于的约束。观察这\(2n-2\)个约束。第一组可以将要求的排成一个不降的序列，然后第二组就是在第一组的基础上再添加条件。

不妨设第一组生成的不降序列是\(\{a_i\}\)，然后添加的条件是\(a_i\leqslant a_j\)。那么显然，\(i<j\)的时候这个条件是没有用的。而如果\(i>j\)，就代表着\(i\)到\(j\)这一整个区间都要相等。这个用差分数组标记一下，最后统计即可。

需要注意的是可能可以生成超过\(k\)种字母，也可能大于\(26\)种，所以最后输出的时候对\(k\)取min即可。

参考程序

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

const int Maxn = 200010;
int n, k, P[ Maxn ], Q[ Maxn ], Ref[ Maxn ];
int A[ Maxn ], Ans[ Maxn ];

int main() {
    scanf( "%d%d", &n, &k );
    for( int i = 1; i <= n; ++i ) scanf( "%d", &P[ i ] );
    for( int i = 1; i <= n; ++i ) scanf( "%d", &Q[ i ] );
    for( int i = 1; i <= n; ++i ) Ref[ P[ i ] ] = i;
    for( int i = 1; i < n; ++i ) 
        if( Ref[ Q[ i + 1 ] ] < Ref[ Q[ i ] ] )
            ++A[ Ref[ Q[ i + 1 ] ] ], --A[ Ref[ Q[ i ] ] ];
    int Sum = 0;
    for( int i = 1; i <= n; ++i ) {
        if( Sum ) Ans[ i ] = Ans[ i - 1 ]; else Ans[ i ] = Ans[ i - 1 ] + 1;
        Sum += A[ i ];
    }
    if( Ans[ n ] < k ) 
        printf( "NO\n" );
    else {
        printf( "YES\n" );
        for( int i = 1; i <= n; ++i ) printf( "%c", min( Ans[ Ref[ i ] ], k ) + 'a' - 1 );
        printf( "\n" );
    }
    return 0;
}