CF1607D Blue-Red Permutation 题解 » 老官童鞋gogo的博客

传送门

题目强调与分析

翻译本题：给出一串长度为 $n$ 的字符串，其中只包含 “$B$” ， “$R$” 两种字符，分别表示蓝色和红色，每一个字符还附有一个值，对于每次操作，你可以选择其中一个字符，对它的值进行以下两种修改：

如果颜色是红色，可以通过一次操作将它的值 $+1$ ；
如果颜色是蓝色，可以通过一次操作将它的值 $-1$ ；

求：是否存在一种方案，将整个序列的值修改为 $1$~$n$ 的排列（不考虑顺序）。共 $T$ 组数据（对于部分多组数据题目，要记得初始化变量、数组）。

题解

这道题目我第一眼看成是用线段树做法（个人理解，未使用代码验证正确性），将一对字符和值看作是一个不等式，例如 “$R$-$5$” ，会被记作 $x \ge 5$ ， “$B$-$3$” ，会被记作 $x \le 3$ ，然后分别在区间 $[5,n]$ 和区间 $[1,3]$ 范围 $+1$ ，最后将线段树上所有的叶子节点拿出来排序，如果排序的结果为单调递增，则输出YES，否则输出NO。这种方法时间复杂度为 $O(n \log n)$ ，常数很大，代码写起来很麻烦。

另外一种更优的做法，先将输入的字符与值根据颜色不同分类，对蓝色与红色的数组分别维护，对分类后的数组从小到大排序，从第小数开始枚举，如果当前的蓝色数组能够取到符合要求的数，就优先取蓝色的，为什么？根据贪心，红色的值只会变大不会变小，蓝色的值只会变小不会变大，所以蓝色的值越小，红色的值越大，它们所能修改到的数越少。因此对于一些小数，我们尽量用蓝色数组中的更小的值转化而来，这样会使这些数字发挥更大的作用，因为那些较大的数不能用蓝色数组中较小的值取到，反观红色，亦是如此。所以若是数字从小到大枚举，需要优先选取蓝色数组中的值。这钟方法，时间复杂度为 $O(n \log n)$ ，复杂度主要来自于排序。

既然主要复杂度来自于排序，那么我们可以继续在排序上优化。本题 $1\le n \le 2 \times 10^5$ ，数据不大，所以可以使用桶排序，但是 $−10^9 \le a_i \le 10^9$ ，没有关系，因为我们要求的是 $1$~$n$ 的排列，对于超过这个范围的数据可以提前处理掉，例如：

蓝色数组中值小于 $1$ 的与红色数组中值大于 $n$ 的，只要存在，就可以直接输出NO。
蓝色数组中大于 $n$ 的值能够变换到 $1 \sim n$ 中的任意值，它与蓝色数组中为 $n$ 的值是等价的。红色数组中小于 $1$ 的值能够变换到 $1 \sim n$ 中的任意值，它与红色数组中为 $n$ 的值是等价的。可以将它们分别处理为与其等价的结果。

如此，时间复杂度降为 $O(n)$ 。

代码

本题只使用了时间复杂度为 $O(n \log n)$ 的做法。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define LL long long
#define uLL unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000001
template<class T>inline void read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar('0'+x%10);
}
int t,a[M],b[M],r[M];
int main()
{
    read(t);
    while(t--)
    {
        int n,lenr=0,lenb=0;
        char c;
        read(n);
        for(int i=1;i<=n;i++)
        {
            read(a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%c",&c);
            if(c=='R')
                r[++lenr]=a[i];
            else
                b[++lenb]=a[i];
        }
        sort(b+1,b+1+lenb);
        sort(r+1,r+1+lenr);
        int i=0,j=0;
        while(1)
        {
            if(i==lenb&&j==lenr)
            {
                break;
            }
            if(i<lenb&&j<lenr)
            {
                if(b[i+1]>=i+j+1)
                    i++;
                else if(r[j+1]<=i+j+1)
                    j++;
                else
                    break;
            }
            else if(j==lenr)
            {
                if(b[i+1]>=i+j+1)
                    i++;
                else
                    break;
            }
            else if(i==lenb)
            {
                if(r[j+1]<=i+j+1)
                    j++;
                else
                    break;
            }
        }
        if(i==lenb&&j==lenr)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}