第36个点TLE求助
查看原帖
第36个点TLE求助
424052
reailikezhu楼主2021/8/5 15:49
#include<stdio.h>
#include<queue>
#include<string.h>

using std::priority_queue;
using std::pair;
using std::make_pair;

int a[50010],b[50010];
char s[50010],str[50010];
int len,l,r;
long long ans;
priority_queue<pair<int,int> >Q;

int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }

int main(){
	scanf("%s",s);
	for(int i=0;i<strlen(s);i++) str[i]=s[i];
	for(int i=0;i<strlen(s);i++){
		if(s[i]=='(') l++;
		if(s[i]==')') r++;
		if(s[i]=='?'){
			str[i]=')';
			scanf("%d%d",&a[i],&b[i]);
			len++;
		}
	}
	if(s[0]==')'||s[strlen(s)-1]=='('){
		printf("-1");
		return 0;
	}
	if(max(l,r)-min(l,r)>len){
		printf("-1");
		return 0;
	}
	l=r=0;
	if(s[0]!='(') str[0]='(';
	l++;
	for(int i=1;i<strlen(s);i++){
		if(s[i]=='?') Q.push(make_pair(b[i]-a[i],i));
		if(str[i]=='(') l++;
		if(str[i]==')') r++;
		if(r>l){
			pair<int,int> p=Q.top();
			Q.pop();
			int x=p.second;
			r--;
			l++;
			str[x]='(';
		}
	}
	if(l!=r){
		printf("-1");
		return 0;
	}
	if(str[0]!='('||str[strlen(str)-1]!=')'){
		printf("-1");
		return 0;
	}
	for(int i=0;i<strlen(s);i++){
		if(s[i]=='?'){
			if(str[i]=='(') ans+=a[i];
			if(str[i]==')') ans+=b[i];
		}
	}
	printf("%I64d\n%s",ans,str);
	return 0;
} 
2021/8/5 15:49
加载中...