比赛链接: Codeforces Round 995

Github 链接: CF995

A. Preparing for the Olympiad

当 $a_i>b_{i+1}$ 时，将 $a_i-b_{i+1}$ 加入答案。最后将 $a_n$ 加入答案。

时间复杂度： $O(tn)$

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

const int N = 105;
int a[N], b[N], n;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int main() {
	int t = read();
	while (t--) {
		n = read();
		for (int i = 1; i <= n; i++) a[i] = read();
		for (int i = 1; i <= n; i++) b[i] = read();
		int ans = 0;
		for (int i = 1; i < n; i++) ans += a[i] - b[i + 1] > 0 ? a[i] - b[i + 1] : 0;
		ans += a[n];
		printf("%d\n", ans);
	}
	return 0;
}

B. Journey

将 $a$, $b$, $c$ 连着三天记为一轮，先算出总共走的完整轮数 $\lfloor \frac{n}{a+b+c}\rfloor$，最后再算剩下的路程 $n$ % $(a+b+c)$ 需要走多少天。

时间复杂度： $O(t)$

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

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int main() {
	int t = read();
	while (t--) {
		int n = read(), a = read(), b = read(), c = read();
		int ans = n / (a + b + c) * 3;
		n %= (a + b + c);
		if (n > 0) ans++, n -= a;
		if (n > 0) ans++, n -= b;
		if (n > 0) ans++, n -= c;
		printf("%d\n", ans);
	}
	return 0;
}

C. Preparing for the Exam

• 如果 $k<n-1$，那么不管是什么样的 $list$ 都无法通过。
• 如果 $k=n$，那么可以通过所有的 $list$。
• 如果 $k=n-1$，那么只有当 $q_{1\le i\le k}$ 恰好为 $a$ 中没有出现的 $[1,n]$ 的整数时可以通过。

时间复杂度： $O(t(n+m+k))$

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

const int N = 3e5 + 10;
int n, m, k, a[N], q, vis[N];

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

int main() {
	int t = read();
	while (t--) {
		n = read(), m = read(), k = read();
		for (int i = 1; i <= n; i++) vis[i] = 1;
		for (int i = 1; i <= m; i++) a[i] = read();
		for (int i = 1; i <= k; i++) q = read(), vis[q] = 0;
		if (k < n - 1) {
			for (int i = 1; i <= m; i++) putchar('0');
			puts("");
			continue;
		}
		if (k == n) {
			for (int i = 1; i <= m; i++) putchar('1');
			puts("");
			continue;
		}
		for (int i = 1; i <= m; i++) {
			if (vis[a[i]]) putchar('1');
			else putchar('0');
		}
		puts("");
	}
	return 0;
}

D. Counting Pairs

题目只关心选的两个数的大小，不关心数的位置，所以可以直接对 $a$ 数组进行排序。排序后枚举整数对的第一个数 $l$，第二个数 $r$ 满足 $x\le sum-a[l]-a[r]\le y$，即

$$\begin{array}{c}a[r]\le sum-a[l]-x\\ a[r]\ge sum-a[l]-y\end{array}$$

时间复杂度： $O(tn\log n)$

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

#define int long long

const int N = 2e5 + 10;
int n, x, y, a[N], sum;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

signed main() {
	int t = read();
	while (t--) {
		n = read(), x = read(), y = read(), sum = 0;
		for (int i = 1; i <= n; i++) a[i] = read(), sum += a[i];
		sort(a + 1, a + n + 1);
		int ans = 0;
		for (int l = 1; l <= n; l++) {
			if (sum - a[l] < x) break;
			int L = lower_bound(a + 1, a + n + 1, sum - a[l] - y) - a;
			int R = upper_bound(a + 1, a + n + 1, sum - a[l] - x) - a - 1;
			if (L <= R && R > l) ans += min(R - L + 1, R - l);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

E. Best Price

在购买人数相同（比单价小的 $b$ 数量一定）并且满足不超过 $k$ 个差评的前提下，我们要让单价尽可能的大，因此单价一定为 $a$, $b$ 数组中的某一个值。
因此，只需要枚举 $a$, $b$ 中的每一个值作为商品单价，检查这个单价是否满足不超过 $k$ 个差评的条件，最后算出这个单价下的总利润。

根据题目描述可以发现最终结果与 $a$, $b$ 的顺序无关：

• 是否购买由 $b$ 决定，单价一定的情况下，无论如何调整顺序不会影响购买人数。
• 购买的所有人中，所有人的 $b$ 一定都大于等于单价，因此好评与差评只与 $a$ 的大小有关，无论如何调整 $a$ 数组的顺序， $a$ 与单价之间的大小关系不会改变。

因此可以分别对 $a$, $b$ 数组进行排序。

每次都可以利用二分分别在 $a$, $b$ 数组中差评个数和购买人数，然后直接计算出总利润。

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

#define int long long

const int N = 2e5 + 10;
int n, k, a[N], b[N], p[N << 1];

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

signed main() {
	int t = read();
	while (t--) {
		n = read(), k = read();
		for (int i = 1; i <= n; i++) a[i] = read();
		for (int i = 1; i <= n; i++) b[i] = read();
		sort(a + 1, a + n + 1), sort(b + 1, b + n + 1);
		int pp = 1, p1 = 1, p2 = 1;
		while (p1 <= n || p2 <= n) {
			if (p1 > n) p[pp++] = b[p2++];
			else if (p2 > n) p[pp++] = a[p1++];
			else if (a[p1] > b[p2]) p[pp++] = b[p2++];
			else p[pp++] = a[p1++];
		}
		int ans = 0;
		for (int i = 1; i <= 2 * n; i++) {
			int pos = lower_bound(a + 1, a + n + 1, p[i]) - a - 1;
			int idx = lower_bound(b + 1, b + n + 1, p[i]) - b;
			if (pos - idx + 1 <= k) ans = max(ans, p[i] * (n - idx + 1));
		}
		printf("%lld\n", ans);
	}
	return 0;
}

时间复杂度： $O(tn\log n)$