[ACM]【greedy】Atcoder 167 Bracket Sequencing

标签: 基础

Bracket Sequencing

传送门
题意:给出n条串,每一条为空、一个或多个’(‘以及’)'组成,要求组合这n条串(全部都要用到),如果能够得到要么为空,要么满足左括号右括号一一对应的串(如"(((())))"、"(()()())"、“空”),则输出yes,否则输出no。
题目图片

思路:

长度放在这里,数目放在这里,题号放在这里,暴力?O(n^2)?想peach。
如果要O(n),据我个人的经验,要么可以推出数学公式,要么可以贪心找到特殊状态一判断就能得到答案。
这题都给这么多括号了,让我很容易联想到prefix啊…。

在草稿纸上画了画,找到每条字串达到一一对应仍所需要的右括号数rr,和所需要的左括号数ll,塞进按照贪心状态排列的优先队列,一判断则得到答案。

这个贪心状态就是:
首先,rr大于ll的字串肯定往左边放,ll大于rr的肯定往右边放,这样先分成两块。在前一块里面,需要rr越多,越往左放;后一块里面,需要ll越多,越往右放。

当然因为使用了优先队列,所以考虑减少一下数目,把rrll都为0的字串直接丢掉,因为这种字串不影响结果。

最后得到的字串队列,直接从左到右扫过去看看满不满足一一对应即可。

那么如何计算rrll呢?很简单,先把字串画出来,就可以发现,从左到右,如果r=0r=0,遇到’)’,就加ll,如果r!=0r!=0,就减rr;遇到((时,直接加rr即可。(都是靠画字串模拟的)

贴一下题解给出的计算rrll的方法:(其实我妹看懂)
llAiA_irrBiB_i
在这里插入图片描述

代码:

#include<bits/stdc++.h>
using namespace std;
char str[1000005];
struct node{
	int l,r;
	bool operator <(node b)const{
		//原来是从大轮到小。 
		//return 0:前者置前,b置后 
		//return 1:后者置前,b置前 
		if(r-l>=0) {
			if(b.r-b.l<=0) return 0;
			else return b.l<l;
		}
		else if(r-l<=0) {
			if(b.r-b.l>=0) return 1;
			else return b.r>r;
		} 
	}
};
int main(){
	int n;
	scanf("%d",&n);
	getchar();
	priority_queue<node>pq;
	for(int i=1;i<=n;i++) {
		//用fgets才能扫进空字串
		fgets(str,1000005,stdin);
		str[strlen(str)-1]='\0';
		int l=0,r=0;
		for(int j=0;j<strlen(str);j++){
			if(str[j]=='(') r++;
			else{
				if(r!=0) r--;
				else l++;
			}
		}
		if(l==0&&r==0) continue;
		pq.push(node{l,r});
	}
	int l=0,r=0;
	//特判全空,不然下面取出会RE
	if(pq.empty()){
		printf("Yes\n");
		return 0;
	}
	node cur=pq.top();
	pq.pop();
	l=cur.l,r=cur.r;
	while(!pq.empty()){
		cur=pq.top();
		pq.pop();
		int tl=cur.l,tr=cur.r;
		//其实就是从左至右更新r和l
		if(r>tl) {
			r-=tl;
			r+=tr;
		}
		else {
			l+=(tl-r);
			r=tr;
		}
		if(l!=0) break;
	}
	if(r==0&&l==0) printf("Yes\n");
	else printf("No\n");
} 
版权声明:本文为weixin_45497996原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45497996/article/details/106292221