Acwing.第116场周赛

这次做的稍微通畅一点,但是做到第三题还是发懒了,以后每次周赛打完都会有一个周赛总结

第一题:简单判断

给定三个非负整数 x,y,z ,请根据如下要求进行判断并输出结果:

如果 x>y+z,输出+;
如果 y>x+z,输出-;
如果x=y并且z=0,则输出0;
如果以上都不满足,则输出?

不难发现,本题不存在同时满足多个条件的情况

输入格式
共一行，三个非负整数 x,y,z。
输出格式
共一行，输出相应结果。
测试样例
输入样例1：
1 1 0
输出样例1：
0
输入样例2
2 0 1
输出样例2
+
这个题一眼模拟，很好写，就不做过多解释了

#include<bits/stdc++.h>
using namespace std;
int main(){
	int x,y,z;
	cin>>x>>y>>z;
	if(x==y&&z==0){
		cout<<0<<endl;
	}
	else if(x>(y+z)){
		cout<<"+"<<endl;
	}
	else if(y>(x+z)){
		cout<<"-"<<endl;
	}
	else{
		cout<<"?"<<endl;
	}
	return 0;	
}

第二题奶牛用餐

约翰的农场有 n头奶牛，编号 1∼n。
每天奶牛们都要去食堂用餐。
食堂一共有 k个座位，也就是说同一时间最多可以容纳 k头奶牛同时用餐。
已知，第 i 头奶牛到达食堂的具体时刻为 si，用餐所需花费的时间为 ti。
保证 s1<s2<…<sn。
为了让奶牛们有序用餐，约翰制定了如下规则：
每头奶牛都必须由约翰安排座位用餐。
每头奶牛从到达食堂的那一刻起，即刻进入待安排状态。
任意时刻，只要存在空座位以及待安排奶牛，约翰就会即刻安排奶牛就座用餐。
如果某一时刻，空座位的数量少于待安排奶牛的数量，则优先安排编号更小的奶牛就座用餐。
每头奶牛用餐完毕的那一时刻都会被约翰立即轰走，即刻空出座位。
除了用餐花费时间以外，其它花费时间忽略不计。

请你计算并输出，每头奶牛用餐完毕的具体时刻。

输入格式
第一行包含两个整数 n,k。
接下来 n行，其中第 i行包含两个整数 si,ti。
注意，输入保证 s1<s2<…<sn。
输出格式
共 n行，每行输出一个整数，其中第 i行的整数表示第 i头奶牛用餐完毕的具体时刻。
数据范围
前 3个测试点满足 1≤n≤10。
所有测试点满足 1≤n,k≤5×10^{5,1≤si,ti≤10}9。
样例测试
输入样例1：
3 2
1 5
2 5
3 5
输出样例2：
6
7
11
这个题也是一个简单题，可以用优先队列把这个题秒了，虽然是按照序号用餐，但我们还是优先考虑吧占用座位时间少的地方，这样他就能先出去，因此用个优先队列将用时间短的始终放在前面，同时题中也给了我们队列的长度限制，即座位个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10;
int a[N];
int main(){
	int n,k;
	cin>>n>>k;
	priority_queue<ll, vector<ll>, greater<ll> > q;
	while(n--){
		ll a,b;
		cin>>a>>b;
		if(q.size()<k){
			q.push(a+b);
			cout<<a+b<<endl;
		}
		else{
			auto it=q.top();
			q.pop();
			cout<<max(it,a)+b<<endl;
			q.push(max(it,a)+b);
		}
	}
	return 0;	
}

第三题平衡括号字符串

给定一个字符串 s，该字符串的每个字符都是 (、) 或 # 之一。
你的任务是将 s中的每个 # 变换为一个或多个 )，从而得到一个平衡括号字符串。
不同 # 变换的 ) 的数量可以不同。
请你输出为了满足条件，每个 # 所需变换的 ) 的数量。
如果方案不唯一，则输出任意合理方案均可。
当一个字符串满足以下所有条件时，该字符串被称为平衡括号字符串：
字符串仅由 ( 和 ) 组成。
字符串所包含的 ( 和 ) 的数量相同。
对于字符串的任意前缀，其所包含的 ( 的数量都不少于 ) 的数量。
输入格式
共一行，一个字符串 s。
输入保证 s中至少包含一个 #。
输出格式
如果不存在任何合理方案，则输出 -1 即可。
如果存在合理方案，则按照从左到右的顺序，对于 s中的每个 #，输出一行一个正整数，表示该 # 所需变换的 ) 的数量。
如果方案不唯一，则输出任意合理方案均可。
数据范围
前 6个测试点满足 1≤|s|≤20。
所有测试点满足 1≤|s|≤10^5。
样例测试
输入样例1：
(((#)((#)
输出样例1：
1
2
输入样例2：
（#）
输出样例2：
-1
这个题有点类似于栈的问题，我们需要统计一下字符串中有多少个#，且字符串中是否存在（）两种字符的差值

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int ans=0;
	int cnt=0;
	int pos;

	for(int i=0;i<s.size();i++){
		if(s[i]=='('){
			ans++;
		}
		else if(s[i]==')'){
			ans--;
		}//记录()差
		else{
			cnt++,pos=i;//记录#字符的个数，以及最后一次出现的位置

		}
	}
	if(ans<cnt){
		cout<<-1<<endl;
		return 0;
	}//如果本身差小于#字符的个数，那就无法保证每个#可以变成一个)
	//接下来我们再一次统计，我们可以现将除最后一个#的位置上全变成一个),再对改变后的字符串进行判断，以防出现不匹配的情况，那么也输出-1
	for(int i=0,sum=0;i<s.size();i++){
		if(s[i]=='('){
			sum++;
		}
		else if(s[i]==')'){
			sum--;
		}
		else if(i!=pos){
			sum--;
		}
		else{
			sum-=ans-cnt+1;

		}
		if(i<s.size()-1&&sum<0){
			cout<<-1<<endl;
			return 0;

		}
		else if(i==s.size()-1&&sum){
			cout<<-1<<endl;
			return 0;

		}
	}
	for(int i=0;i<cnt;i++){
		if(i!=cnt-1){
			cout<<1<<endl;
		}
		else{
			cout<<ans-cnt+1<<endl;
		}
	}
	return 0;
}