CF1599
Bubble Cup 14 - Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred, Div. 1)
CF1599A
题意
给你一个长度为 \(N\) 的质量为 \(A_1,A_2,\dots,A_N\) 的数组 \(A\)。每个数组中的值表示各个砝码的重量。
所有砝码的质量均不相同。你可以把每个砝码放在天平的一边（左边或右边）。
你不必按照 \(A_1,\dots,A_N\) 的顺序放置砝码。还有一个由字符 \(\texttt{L}\) 和 \(\texttt{R}\) 组成的字符串 \(S\)，意思是在放完第 \(i\) 个砝码（不是 \(A_i\) ，而是选择第 \(i\) 个砝码）后，天平的左边或右边应该更重。
找出在天平上放置砝码的顺序，以便满足字符串 \(S\) 的规则。
\(n \le 2\times 10^5\)
题解
很神仙的思路。
首先发现样例中没有 \(-1\)，猜测一定有解。
然后就相当于给出一个构造方案。
数组顺序没有影响，直接排序。
考虑倒着做，将每次填入一个数变成每次删除一个数。
有一个大胆的想法：初始状态让两个天平交替填入 \(1,2,\dots,n\)。
然后发现，每次拿出全局最小值一定不影响倾斜方向，拿出全局最大值一定影响倾斜方向。
证明显然。
然后就做完了（）
代码
#include<bits/stdc++.h>
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10;
int n;
int a[maxn];
char ch[maxn];
bool flag[maxn];//1 = L, 0 = R;
deque<int> L,R;
pair<int,char> ans[maxn];
void main(){
n = read();
for(int i = 1;i <= n;i++)a[i] = read();
scanf("%s",ch + 1);sort(a + 1,a + 1 + n);
for(int i = 1;i <= n;i++){
flag[i] = ch[i] == 'L';
if(i & 1){L.push_back(a[i]);}
else {R.push_back(a[i]);}
}
if(flag[n] != (n & 1)){swap(L,R);}
for(int i = n;i >= 1;i--){
int flg = flag[i] ^ flag[i - 1];
pair<int,char> ll,rr;
ll = rr = make_pair(flg ? -0x3f3f3f3f : 0x3f3f3f3f, 'O');
if(L.size()){ll = make_pair(flg ? L.back() : L.front(),'L');}
if(R.size()){rr = make_pair(flg ? R.back() : R.front(),'R');}
if((ll < rr) ^ flg){ans[i] = ll;if(flg)L.pop_back();else L.pop_front();}
else {ans[i] = rr;if(flg)R.pop_back();else R.pop_front();}
}
for(int i = 1;i <= n;i++){printf("%d %c\n",ans[i].first, ans[i].second);}
return;
}
};
bool edmemory;
signed main(){
auto stclock = clock();
Call_me_Eric::main();
auto edclock = clock();
cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
return 0;
}