讨论详情 - QY code

A.Accidental Victory

思路

每次比赛相当于合并两名选手的筹码，胜者获得两者筹码之和。因此，最终冠军的筹码数等于所有选手筹码的总和。某位选手能获胜，当且仅当存在一种比赛顺序，使得他能不断打败并吞并其他选手，最终收集全部筹码。

将选手按筹码数从小到大排序，并维护一个前缀和 sum。遍历排序后的选手：

如果当前选手的筹码数 a[i] > sum，说明前面所有人的筹码加起来都打不过他，那么他无法被前面的任何人吞并，同时他可以直接吞并前面所有人（因为他比前面总和还大）。因此，从这位选手开始，所有选手都有获胜可能，而之前的选手都没有可能。
更新 pos = i 作为可行起点。
然后 sum += a[i]。

最后，从 pos 到末尾的所有选手都是有可能获胜的。收集他们的原编号，按升序输出。

具体流程

读入 t
循环每个测试用例：
读入 n 和数组 a，同时记录每个选手的原始编号（1-based）
将选手按筹码数从小到大排序
初始化 sum = 0, pos = 0
遍历排序后的选手： - 如果 a[i] > sum，则 pos = i
- sum += a[i]
从 pos 到 n-1 的所有选手都是有获胜可能的
收集这些选手的原始编号，排序
输出数量，然后输出编号（空格分隔）

题解

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

int t;

int main() {
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<pair<long long, int>> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i].first;
			a[i].second = i + 1;
		}
		sort(a.begin(), a.end());
		vector<int> ans;
		long long sum = 0;
		int pos = 0;
		for (int i = 0; i < n; i++) {
			if (a[i].first > sum) {
				pos = i;
			}
			sum += a[i].first;
		}
		for (int i = pos; i < n; i++) {
			ans.push_back(a[i].second);
		}
		sort(ans.begin(), ans.end());	
		cout << ans.size() << '\n';
		for (int i = 0; i < ans.size(); i++) {
			if (i) cout << ' ';
			cout << ans[i];
		}
		cout << '\n';
	}	
	return 0;
}

B.Two TVs

思路

题目本质是判断能否用两台电视覆盖所有区间，且端点不能相接（一个结束时刻等于另一个开始时刻时，不能在同一台电视上连续播放）。把每个节目看成一个区间 [l, r]。按开始时间排序，用两个变量记录两台电视当前播放节目的结束时间。

依次安排每个节目，优先放在结束时间更早的那台电视上

如果某台电视的结束时间 < 当前节目的开始时间，则可以放在这台电视上（更新结束时间为当前节目的 r）
如果两台电视的结束时间都 >= 当前节目的开始时间，说明没有电视可用，输出 NO

具体流程

读入 n 和所有区间 [l, r]
按 l（开始时间）从小到大排序
初始化 end1 = -1，end2 = -1（两台电视当前节目的结束时间）
遍历每个节目 [l, r]：

如果 end1 <= end2：优先用电视 1。如果 end1 < l，将电视 1 的结束时间更新为 r。否则尝试电视 2。
如果 end2 < l，将电视 2 的结束时间更新为 r。否则输出 NO
否则 end2 < end1 ：优先用电视 2。如果 end2 < l，将电视 2 的结束时间更新为 r。否则尝试电视 1。
如果 end1 < l，将电视 1 的结束时间更新为 r。否则输出 NO
全部安排完成 → 输出 YES

题解

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

int n;

int main() {
	cin >> n;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());
	int end1 = -1, end2 = -1;
	for (int i = 0; i < n; i++) {
		int l = a[i].first, r = a[i].second;	
		if (end1 <= end2) {
			if (end1 < l) {
				end1 = r;
			} else if (end2 < l) {
				end2 = r;
			} else {
				cout << "NO\n";
				return 0;
			}
		} else {
			if (end2 < l) {
				end2 = r;
			} else if (end1 < l) {
				end1 = r;
			} else {
				cout << "NO\n";
				return 0;
			}
		}
	}
	cout << "YES\n";
	return 0;
}

C.Potions (Easy Version) && F.Potions (Hard Version)

（两题思路是一样的，无非是数据范围变大了）

思路

从左到右依次经过每瓶药水。遇到正数药水，直接喝下。遇到负数药水，先假设喝下，如果生命值变成负数，就丢弃掉之前喝过的副作用最大的那瓶负数药水（即最小的负数，也就是减生命值最多的那瓶），让生命值恢复。

用优先队列维护所有已经喝下的负数药水。每次加入负数后若生命值 < 0，就弹出堆顶（最小的负数，即副作用最大的），并从生命值中减去它的影响。这样能保证在喝下最多药水的前提下，生命值一直非负。

具体流程

读入 n 和数组 a
初始化 hp = 0，ans = 0，优先队列 pq（大根堆，存负数药水）
遍历每瓶药水 x： a. 如果是正数（x >= 0）：直接喝下，hp += x，ans++ b. 如果是负数（x < 0）：先假设喝下，hp += x，ans++，把 x 加入 pq。
- 如果 hp < 0：从 pq 中取出最小值（副作用最大的负数药水）
  hp -= 取出的值（即去掉这瓶药水的影响）
  ans--
输出 ans

题解

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

int n;

int main() {
	cin >> n;
	priority_queue<int> pq;
	long long hp = 0, ans = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x >= 0) {
			hp += x;
			ans++;
		} else {
			hp += x;
			pq.push(-x);
			if (hp < 0) {
				int top = pq.top();
				pq.pop();
				hp += top;
			} else {
				ans ++;
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

D.Minimize the error

思路

操作可以对 A ± 1，也可以对 B ± 1。本质上，每次操作都可以让某个差值 d[i] = a[i] - b[i] 向 0 靠近 1 或远离 1。为了让误差最小，所有操作都应该用来减小差值（即让差值更接近 0），而不是增大差值。

把 k = k1 + k2 次操作全部用在差值上：每次操作可以让一个 |d[i]| 减少 1（如果 |d[i]| > 0），或者让一个 0 变成 1（如果所有差值都已经为 0，剩余操作只能增大误差）。

所以贪心策略：每次选择当前绝对值最大的差值，将其绝对值减 1。重复 k 次，最后求平方和。

具体流程

读入 n, k1, k2，令 k = k1 + k2
读入数组 A 和 B
计算差值 d[i] = abs(A[i] - B[i])
用大根堆存储所有差值
循环 k 次：

a. 取出堆顶 x（当前最大差值）

b. 如果 x > 0：x--，放回堆

c. 如果 x == 0：x = 1，放回堆（所有差值都已为0，剩余操作只能增加误差）
堆中所有值的平方和即为答案

题解

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

const int N = 1e3 + 5;
int n, k1, k2;
long long a[N], b[N];

int main() {
	
	cin >> n >> k1 >> k2;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];
	priority_queue<long long> pq;
	for (int i = 0; i < n; i++) {
		pq.push(abs(a[i] - b[i]));
	}
	int k = k1 + k2;
	for (int i = 0; i < k; i++) {
		long long x = pq.top();
		pq.pop();
		if (x > 0) x--;
		else x = 1;
		pq.push(x);
	}
	long long ans = 0;
	while (!pq.empty()) {
		long long x = pq.top();
		pq.pop();
		ans += x * x;
	}
	cout << ans << '\n';
	return 0;
}

E.Playlist

思路

按美丽度从大到小排序，然后依次遍历每首歌曲作为"最小美丽度"。用最小堆维护已选歌曲的长度，当堆中歌曲数量超过 k 时，弹出长度最小的（因为我们要让总长度尽可能大）。当前美丽度作为最小值，总愉悦度 = 当前美丽度 × 堆中长度之和。遍历过程中更新最大值。

具体流程

读入 n, k 和所有歌曲 (t, b)
按美丽度 b 从大到小排序
初始化 sum = 0，答案 ans = 0，最小堆 pq
遍历每首歌曲（按美丽度从大到小）：

a. 将当前歌曲长度 t 加入堆，sum += t

b. 如果堆大小 > k：
```
 弹出堆顶（最小的长度），sum -= 弹出的长度
```
c. 当前最小美丽度 = 当前歌曲的 b

d. 愉悦度 = sum * b

e. ans = max(ans, 愉悦度)
输出 ans

题解

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

const int N = 3e5 + 5;
int n, k;
vector<pair<int, int>> songs(N);
priority_queue<int, vector<int>, greater<int>> pq;

bool cmp(pair<int, int> x, pair<int, int> y) {
	return x.second > y.second;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> songs[i].first >> songs[i].second;
	}
	sort(songs.begin(), songs.end(), cmp);
	long long sum = 0, ans = 0;
	for (int i = 0;i < n;i++) {
		int t = songs[i].first;
		int b = songs[i].second;
		pq.push(t);
		sum += t;
		if (pq.size() > k) {
			sum -= pq.top();
			pq.pop();
		}
		ans = max(ans, sum * b);
	}
	cout << ans << '\n';
	return 0;
}

7月Day4

0 条评论

目前还没有评论...

7月Day4

0 条评论

目前还没有评论...

还没有账户？

登录