526互联

CF1599A. Weights

发布时间 2023-04-09 21:05:09作者: gmh77

题意

给出n个物品，第i个重量a[i]（互不相同）
每次任意选一个物品放到秤的左右两边，使得放完之后 左>右 或 左<右
给出a[i] 和 大小关系s[i]，构造方案

题解

必定有解

把a排序，假设当前选了LRLRLR，发现在最后加L可以瞬间反转，在最前加R可以保持不变

即，当前选了一段连续的a[i]，放的顺序为...LRLRLR...，
可以在头部放一个相反的来 保持大小不变+保证交替序列，在尾部放一个相反的来 改变大小关系+保证交替序列

发现有多少段就要在尾部加上多少次（包括第一个），这样放完之后刚好到n，所以可以倒推出第一个选的a[]

然后按顺序扩展，维护a的选择区间（以及交替情况，当前的每个a[i]在哪一边p[i]，实际由于是交替所以(i+p[i])%2相同），构造即可

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
//#define file
using namespace std;

int n,i,j,k,l;
int a[200001];
char S[200001];
ll sumL,sumR;
pair<int,int> ans[200001];
//deque<pair<int,int> > d;
int L,R;

//bool operator < (type a,type b)
//{
//	return a.s<b.s || a.s==b.s && a.x<b.x;
//}
int get(char c)
{
	if (c=='L') return 0;
	return 1;
}

int main()
{
	#ifdef file
	freopen("CF1599A.in","r",stdin);
	#endif
	
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	scanf("%s",S+1);
	
	l=0;
	fo(i,1,n) l+=(i==1) || S[i]!=S[i-1];
	
	l=n-l+1; //l+get(S[1])-L=get
	L=R=l;
	ans[1]=pair<int,int>(a[l],get(S[1]));
	fo(i,2,n)
	if (S[i]==S[i-1])
	{
		--L;
		ans[i]=pair<int,int>(a[L],((l+get(S[1])-L)%2+2)%2);
	}
	else
	{
		++R;
		ans[i]=pair<int,int>(a[R],((l+get(S[1])-R)%2+2)%2);
	}
	
	fo(i,1,n)
	printf("%d %c\n",ans[i].first,(ans[i].second==0)?'L':'R');
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}