Codeforces Round 995 (Div.3)
比赛链接: Codeforces Round 995
Github 链接: CF995
A. Preparing for the Olympiad
当 a i > b i + 1 a_i > b_{i + 1} ai>bi+1 时，将 a i − b i + 1 a_i - b_{i + 1} ai−bi+1 加入答案。最后将 a n a_n an 加入答案。
时间复杂度： O ( t n ) O(tn) 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 a a, b b b, c c c 连着三天记为一轮，先算出总共走的完整轮数 ⌊ n a + b + c ⌋ \left\lfloor\frac{n}{a + b + c}\right\rfloor ⌊a+b+cn⌋，最后再算剩下的路程 n n n % ( a + b + c ) (a + b + c) (a+b+c) 需要走多少天。
时间复杂度： O ( t ) O(t) 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 k < n - 1 k<n−1，那么不管是什么样的 l i s t list list 都无法通过。
- 如果 k = n k = n k=n，那么可以通过所有的 l i s t list list。
- 如果 k = n − 1 k = n - 1 k=n−1，那么只有当 q 1 ≤ i ≤ k q_{1 \le i \le k} q1≤i≤k 恰好为 a a a 中没有出现的 [ 1 , n ] [1, n] [1,n] 的整数时可以通过。
时间复杂度： O ( t ( n + m + k ) ) O(t(n + m + k)) 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 a a 数组进行排序。排序后枚举整数对的第一个数 l l l，第二个数 r r r 满足 x ≤ s u m − a [ l ] − a [ r ] ≤ y x \le sum - a[l] - a[r] \le y x≤sum−a[l]−a[r]≤y，即
a [ r ] ≤ s u m − a [ l ] − x a [ r ] ≥ s u m − a [ l ] − y \begin{matrix} a[r] \le sum - a[l] - x \\ a[r] \ge sum - a[l] - y \end{matrix} a[r]≤sum−a[l]−xa[r]≥sum−a[l]−y
时间复杂度： O ( t n log n ) O(tn\log n) O(tnlogn)
#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
b
b 数量一定）并且满足不超过
k
k
k 个差评的前提下，我们要让单价尽可能的大，因此单价一定为
a
a
a,
b
b
b 数组中的某一个值。
因此，只需要枚举
a
a
a,
b
b
b 中的每一个值作为商品单价，检查这个单价是否满足不超过
k
k
k 个差评的条件，最后算出这个单价下的总利润。
根据题目描述可以发现最终结果与 a a a, b b b 的顺序无关：
- 是否购买由 b b b 决定，单价一定的情况下，无论如何调整顺序不会影响购买人数。
- 购买的所有人中，所有人的 b b b 一定都大于等于单价，因此好评与差评只与 a a a 的大小有关，无论如何调整 a a a 数组的顺序， a a a 与单价之间的大小关系不会改变。
因此可以分别对 a a a, b b b 数组进行排序。
每次都可以利用二分分别在 a a a, b b 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 ( t n log n ) O(tn\log n) O(tnlogn)