题目来源：Codeforces 1468 : 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest

链接：https://vjudge.net/contest/423527

C. Berpizza(数据结构)

题意

在餐馆里有2个服务生，现在以输入执行以下操作：

  • 1 - m：一个即将在餐馆消费m元的顾客进入。
  • 2：服务生A为目前没有接受过服务的顾客中最早进入餐馆的顾客提供服务。输出顾客编号。
  • 3：服务生B为目前没有接受过服务的顾客中期望消费最大的顾客提供服务。输出顾客编号。

操作次数可达$5×10^5$,顾客规模也可达$5×10^5$.不允许暴力。

思路

用优先队列按消费大优先存储服务生B的服务顺序（大顶堆），用一个数组表按进馆顺序存储服务生A的服务顺序。服务生A总是从数组从前往后查询，而服务生B在pop大顶堆的顶部时，也会根据顾客结构体中存储的下标数据改变顾客在对应数组中的状态，达到了二者统一。

复杂度应该是O(nlogn + n)？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
typedef long long ll;
struct node{
	int id, val;
};
int serv[maxn];//为1表示来了但是没有serve 
struct cmp{
	bool operator()(const node &a, const node &b){
		if(a.val != b.val) return a.val < b.val;
		return a.id > b.id;
	}
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	priority_queue<node, vector<node>, cmp> s;
	int pos = 1;
	memset(serv, 0, sizeof(serv));
	int spos = 1;
	while(q--)
	{
		int x;
		cin >> x;
		if(x == 1){
			int m;
			cin >> m;
			s.push({pos, m});
			serv[pos] = 1;
			pos++;
		}
		else if(x == 3){
			while(!serv[s.top().id]){
				s.pop();
			}
			node now = s.top();
			s.pop();
			serv[now.id] = 0;
			cout << now.id << ' '; 
		}
		else if(x == 2){
			while(!serv[spos]){
				spos++;
			}
			cout << spos << ' ';
			serv[spos] = 0;
		}
	}
	return 0;
}

D. Firecrackers(贪心)

分析

因为要保证被抓之前尽可能多地引爆鞭炮，而不管是先跑再扔与先扔再跑，最后被抓的时间都是一样的，故先扔至即将被抓时再跑即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		int n, m, a, b;
		cin >> n >> m >> a >> b;

		int num = abs(b - a) - 1; 
		int catchTime = a - 1;//不能放炸弹的时间
		if(b < a) catchTime = n - a; 
		priority_queue<int> pq;
		int x;
		for(int i = 0; i < m; ++i){
			cin >> x;
			pq.push(x);
		}
		//计算guard与hooligan的距离为num.
		int ans = 0;
		int time = catchTime + num;
		while(!pq.empty())
		{
			if(time >= pq.top())
			{
				ans++;
				time--;
			}
			pq.pop();
		 }
		 cout << min(ans, num) << endl;
	}
	return 0;
}

E. Four Segments(签到)

题意

给四个线段，把他们摆在平面上，要求围出矩形，问矩形最大面积是多少。

分析

四个线段长度排序，按长和宽的短板效应取第一条和第三条长度相乘即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		int a[4];
		for(int i = 0; i < 4; ++i) cin >> a[i];
		sort(a, a + 4);
		cout << a[0] * a[2] << endl;
	}
	return 0;
}

K. The Robot(暴力)

题意

机器人初始在（0,0）.给一个字符串，每一个字符可能代表向上向下向左向右移动。现在要求在平面内一个坐标上放下障碍物，当移动要进入障碍物所在的坐标时，这个移动视为无效。问障碍物应该放在哪里，以保证结束后机器人回到（0,0）.

分析

一开始想了好几种方法，一个个都wa了，这里不贴出来误导……其实5000*5000暴力够了吧。嗯，是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
string s;
typedef long long ll;
inline void move(int& x, int& y, int i)
{
	if(s[i] == 'U') y++;
	else if(s[i] == 'D') y--;
	else if(s[i] == 'L') x--;
	else if(s[i] == 'R') x++;
}
inline void goBack(int& x, int& y, int i)
{
	if(s[i] == 'U') y--;
	else if(s[i] == 'D') y++;
	else if(s[i] == 'L') x++;
	else if(s[i] == 'R') x--;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		cin >> s;
		int nx = 0, ny = 0;
		bool flag = 0;
		for(int i = 0; i < s.size(); ++i)
		{
			move(nx, ny, i);
			int x = 0, y = 0;
			for(int i = 0; i < s.size(); ++i){
				move(x, y, i);
				if(x == nx && y == ny) goBack(x, y, i);
			}
			if(x == 0 && y == 0){
				flag = 1;
				cout << nx << ' ' << ny << endl;
				break;
			}
		}
		if(!flag) cout << "0 0" << endl;
	}
	return 0;
}