题解 CF1599A Weights

Miko35 · 2021-10-11 19:36:59 · 题解

题意概述

给出 n (1 \leq n \leq 2 \times 10^5) 个物品，第 i 个物品重量为 a_i (1\leq a_i \leq 10^9)。你需要将所有物品按照一定的顺序分别摆在天平的左端或右端。

给出一个仅包含 L 与 R 的长度为 n 的字符串，其中第 i 个字符表示，放置完第 i 个物品后，天平的左端 L 或右端 R 更重。你需要构造一种满足字符串限制的放置物品的方案。若无解，输出 -1。

Solution

样例没给 -1 那就是没有，思考通解。

因为是构造题，考虑把规模为 n 的问题转化为规模为 n-1 的问题的套路。

从最终情况（不妨设是 R）倒推，每次取出一个元素。先说结论，将第 1,3,5,\ldots 大的元素放在右边，其他的放在左边，是一种合法的最终情况。

在这种情况下，考虑取出什么元素能够使天平状态不变/改变，且能使问题的形式一样：

• 取出最小的元素，天平状态一定不变。
• 取出最大的元素，天平状态一定改变。

而且在这两种情况下，天平的摆放状况仍然是，物品从小到大摆放左右交替的形式，而规模变为了 n-1。所以模拟即可。

#include<bits/stdc++.h>
#define rgi register int
#define FOR(i,a,b) for(rgi i=a;i<=b;++i)
using namespace std;
const int N=400010;
int n,a[N],ans[N];
char s[N];
signed main(){
    scanf("%d",&n);
    FOR(i,1,n)scanf("%d",&a[i]);
    sort(a+1,a+n+1),scanf("%s",s+1);
    for(rgi l=1,r=n;l<=r;){
        rgi w=r-l+1;
        ans[w]=(s[w]==s[w-1]?l++:r--);
    }
    FOR(i,1,n)printf("%d %c\n",a[ans[i]],"LR"[(ans[i]&1)^(n&1)^(s[n]=='R')]);
    return 0;
}