A. Robin Helps

根据题意写即可

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
#include <iostream>
using namespace std;
#define int long long
const int N = 55;
void solve()
{
	int n, k;
	cin >> n >> k;
	int a[N];
	for (int i = 1; i <= n; i++) cin >> a[i];
	int own = 0, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] >= k) own += a[i];//收钱
		else if (a[i] == 0 && own > 0) own--, ans++;//发钱
	}
	cout << ans << '\n';
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

B. Robin Hood and the Major Oak

第一年有1片树叶，第i年新增\(i^i\)片树叶，树叶可保存k年，问第n年的树叶数是奇数还是偶数

通过分析k，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
#include <iostream>
using namespace std;
#define int long long
void solve()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	if (k % 2) //如果k是奇数
		ans += n % 2;
	if (k / 2 % 2)//有奇数个奇偶数对 
		ans += 1;
	if (ans % 2) cout << "NO" << '\n';
	else cout << "YES" << '\n';	
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

C. Robin Hood in Town

找到最富有的人，问给他多少钱可以保证超过一半的人的钱数小于所有人平均值的一半

注意特判只有一个人或两个人的情况

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
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
void solve()
{
	int n, sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
	if (n == 1 || n == 2)
	{
		cout << -1 << '\n';
		return;
	}
	sort(a + 1, a + n + 1);
	int ans = a[(n + 2) / 2] * 2 * n - sum + 1;
	if (ans <= 0) cout << 0 << '\n';
	else cout << ans << '\n';
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

D. Robert Hood and Mrs Hood

给定k个在1~n上的区间，要求找到和这k个区间相交数最多和最少的、区间长度为d的区间的起点

  1. 正难则反，可以寻找和这k个区间中不相交区间的数量的最大、最小的区间起点
  2. 如果区间的左端点大于r或者右端点小于l，那么这两个区间一定不想交
  3. 用R和L数组记录每个位置左端点和右端点出现的次数
    • L数组利用后缀和，表示以该下标为右端点，其右边（包括自身）有多少个l点
    • R数组利用前缀和，表示以该下标为左端点，其左边（包括自身）有多少个r点
  4. 因为L，R数组记录时是包含自身的，所以在查询的时候分别取前一个点和后一个点满足条件的值
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
#include <iostream>
#include <string>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int R[N], L[N];
void solve()
{
	memset(R, 0, sizeof R);
	memset(L, 0, sizeof L);
	int n, d, k;
	cin >> n >> d >> k;
	while (k--)
	{
		int l, r;
		cin >> l >> r;
		L[l]++, R[r]++;
	}
	//R记录 以该点为左端点在几个r的右边，即问它的左边(或加上自己)有几个r点
	for (int i = 1; i <= n; i++)
		R[i] += R[i - 1];
	//L记录 以该点为右端点在几个l的左边，即问它的右边(或加上自己)有几个l点
	for (int i = n ; i >= 0; i--)
		L[i] += L[i + 1];
	int t = 0, maxn = -0x3f3f3f3f, imax = 0, minn = 0x3f3f3f3f, imin = 0;
	for (int i = 1; i + d - 1 <= n; i++)//列举以每个点为左端点
	{
		t = R[i - 1] + L[i + d];
		if (t > maxn) imax = i, maxn = t;
		if (t < minn) imin = i, minn = t;
	}
	cout << imin << " " << imax << '\n';
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}