题解
题目描述
给你一个长度为 (N) 的质量为 (A_1), (A_2) ... (A_N) 的数组 (A)。每个数组中的值表示各个砝码的重量。 所有砝码的质量均不相同。你可以把每个砝码放在天平的一边（左边或右边）。 你不必按照 (A_1) ,..., (A_N) 的顺序放置砝码。还有一个由字符 "(L)"和 "(R)"组成的字符串 (S) ， 意思是在放完第 (i) 个砝码（不是 (A_i) ，而是选择第 (i) 个砝码）后，天平的左边或右边应该更重。 找出在天平上放置砝码的顺序，以便满足字符串 (S) 的规则。 输入格式 第一行包含一个整数 (N) $( 1≤N≤2∗10^5) $ 第二行包含 (N) 个不同的整数。(A_1) , (A_2) , ..., $A_N ( 1≤Ai≤109) $ 第三行包含长度为 (N) 的 (S) 字符串，仅由字母 "(L) "和 "(R) " 组成。 输出格式 输出包含 (N) 行。在每一行中，你应该打印一个整数和一个字母 -- 整数代表你在那一步中放在天平上的重量，字母代表你放重量的天平的一边。
如果没有解决方案，打印 (-1) 。
解题思路
简单地说，对于每一个和上一个一样的字符，比如 (LLLLLL)，我们就希望一直浑水摸鱼。一个简单的想法是我们 (+5 -4 +3 -2 +1)，这样就能一直摸下去。
所以我们把数分成小的和大的，假设小的是 (a_1<a_2<cdots <a_m)，大的是 (a_{m+1}<a_{m+2}<cdots<a_n)。对于每一个和前一个不一样的，我们就放一个新的大数，一个一个放，这样就能改变局面。对于需要浑水摸鱼的，我们减 (a_m)，加 (a_{m-1})，这样一直摸鱼。就比如一开始是 (L)，那么每次换的时候 (R) 是靠一样多比较大，(L) 是靠多一个数，因为 (L) 多一个数所以给 (L) 一点劣势没关系，所以我们在 (L) 这边一直整活，先 (R) 一个 (a_m)，再 (L) 一个 (a_{m-1})，这样下去。
代码+思路
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3;
int a[N],ans[N];
int n;
char s[N],t[N];
#define fre(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
int main()
{
fre(weight);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);scanf("%s",s+1);
int tt=n&1,l=1,r=n;
for(int i=n;i>1;i--,tt^=1)
if(s[i-1]==s[i])
{
t[i]=tt?s[i]:s[i]=='L'?'R':'L';
ans[i]=a[l++];
}
else
{
t[i]=s[i];
ans[i]=a[r--];
}
ans[1]=a[l];t[1]=s[1];
for(int i=1;i<=n;i++)printf("%d %c
",ans[i],t[i]);
return 0;
}
/*
理论证明见 https://www.luogu.com.cn/problem/solution/CF1599A
我们设 tt=1 表示在同侧取，tt=0 表示在反侧取
那么考虑 n为奇数的情况，此时 tt=1，
那么若此时这个位置 i 与上一个位置 i-1 不相等，
那么我们把奇数放在位置 i 的那一侧，再把它最大的数塞进去，此时奇数小于偶数，并且最小的数在
然后此时，对于 i-1 来说，最小的位置在反侧。tt^=1
若 n 为偶数的情况，此时 tt=1。
那么若此时这个位置 i 与 上一个位置 i-1 不相等。
我们把偶数放在位置 i 的那一侧，再把它最大的数塞进去，此时奇数大于偶数
然后此时，对于 i-1 来说，此时最小的位置在同侧，tt^=1
对于取同侧，最小的数在不断变化，所以需要 tt^=1
那么若这个位置 i 与上一个位置 i-1 相等，那么我们取出
*/