CF1599A 题解

· · 题解

CF1599A 题解

思路分析

首先注意到 a_i 互不相同，因此考虑忽略 a_i 的值域，通过比较 a_i 的排名来构造。

又因为我们的切换过程应该要尽可能得简单，因此我们考虑对 a_i 排序后把奇偶的两项放到天平的两侧，如下图，对于任意一种情况，我们都能给出一种合法的构造：

如上图所示，圆圈中的数表示 a_i 排完序后在序列中的下标。

而当我们从 n\to n+1 转移的情况如下图，依然可以继续做：

我们发现每次转移的时候只会选择当前序列的最大值或最小值，因此我们可以先从左到右扫描一遍，记录一下每次操作选择的放置方向和砝码是当前的最大值还是最小值，最后倒序依次考虑，用 multiset 从后到前依次分配权值。

从上面的分析可以看出，对于任何的一组数据，我们都给出了合法的构造，并且与 a_i 的具体值无关。

时间复杂度 \Theta(n\log n)。

代码呈现

#include<bits/stdc++.h>
#define MIN 0
#define MAX 1
using namespace std;
const int MAXN=2e5+1;
char str[MAXN],op[MAXN];
int a[MAXN],ch[MAXN],val[MAXN];
signed main() {
    int n;
    scanf("%d",&n);
    multiset <int> s;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),s.insert(a[i]);
    scanf("%s",str+1);
    ch[1]=MIN,op[1]=str[1];
    for(int i=2;i<=n;++i) {
        if(str[i-1]=='L') {
            if(i%2==0) {
                if(str[i]=='L') op[i]='R',ch[i]=MIN;
                if(str[i]=='R') op[i]='R',ch[i]=MAX;
            } else {
                if(str[i]=='L') op[i]='L',ch[i]=MIN;
                if(str[i]=='R') op[i]='R',ch[i]=MAX;
            }
        } else {
            if(i%2==0) {
                if(str[i]=='L') op[i]='L',ch[i]=MAX;
                if(str[i]=='R') op[i]='L',ch[i]=MIN;
            } else {
                if(str[i]=='L') op[i]='L',ch[i]=MAX;
                if(str[i]=='R') op[i]='R',ch[i]=MIN;
            }
        }
    }
    for(int i=n;i>=1;--i) {
        if(ch[i]==MIN) val[i]=*s.begin(),s.erase(s.begin());
        if(ch[i]==MAX) val[i]=*prev(s.end(),1),s.erase(prev(s.end(),1));
    }
    for(int i=1;i<=n;++i) printf("%d %c\n",val[i],op[i]);
    return 0;
}