Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

A. Prison Break

https://codeforces.com/contest/1457/problem/A

题意：给定一个n行m列的监狱（每个（i，j)中均有犯人），犯人们为了集体逃脱找到了一个洞口（r,c）点。现在请问最少需要多少秒才能全体逃脱。

思路：只要计算一下边角的犯人离出口的最大距离即可

  1. void solve() {
  2.     int n, m, r, c;
  3.     cin >> n >> m >> r >> c;
  4.     cout << max(r - 1, n - r) + max(c - 1, m - c) << endl;
  5. }

B. Repainting Street

https://codeforces.com/contest/1457/problem/B

题意：Tom要为一排房子粉刷颜色，每个房子的都有它的颜色，由于Tom认为相同颜色的为”美丽“，但Tom每天只能为k个连续的房子进行粉刷。请问最少需要多少天才能变美丽

思路：由于仅100种颜色，可以使用暴力枚举 + 滑动窗口解决

  1. void solve() {
  2.     int n, k;
  3.     cin >> n >> k;
  4.     int a[n + 1];
  5.     for (int i = 0; i < n; ++i)
  6.         cin >> a[i];
  7.     int res = n;
  8.     for (int c = 1; c <= 100; ++c) { //枚举进行粉刷的颜色种类
  9.         int last = -k, curr = 0;
  10.         for (int j = 0; j < n; ++j) {
  11.             if (a[j] == c)
  12.                 continue;
  13.             if (last + k <= j) {
  14.                 last = j;
  15.                 curr++;
  16.             }
  17.         }
  18.         res = min(res, curr);
  19.     }
  20.     printf("%d\n", res);
  21. }

C. Bouncing Ball

https://codeforces.com/contest/1457/problem/C

  1. string s;
  2. void solve() {
  3.     int n, p, k, x, y;
  4.     cin >> n >> p >> k;
  5.     p--;
  6.     vector<int> b(n);
  7.     cin >> s;
  8.     cin >> x >> y;
  9.     int ans = 1 << 30;
  10.     for (int i = n - 1; 0 <= i; --i) {
  11.         b[i] = !(s[i] == '1');
  12.         if (i + k < n)
  13.             b[i] += b[i + k];
  14.         if (i >= p)
  15.             ans = min(ans, (i - p) * y + b[i] * x);
  16.     }
  17.     printf("%d\n", ans);
  18. }

E. New Game Plus!

https://codeforces.com/contest/1457/problem/E

理解好题意，利用前缀和贪心即可

  1. // Author : RioTian
  2. // Time : 20/11/29
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. const int N = 5e5 + 5;
  7. int n, k, a[N];
  8. ll b[N], sum, res = -(1LL << 60), curr;
  9. int main() {
  10.     cin >> n >> k;
  11.     for (int i = 1; i <= n; ++i)
  12.         cin >> a[i];
  13.     sort(a + 1, a + n + 1);
  14.     for (int i = 1; i <= n; ++i) {
  15.         b[i] = b[i - 1] + a[i];
  16.         sum += 1LL * (i - 1) * a[i];
  17.     }
  18.     for (int i = 1; i <= n; ++i) {
  19.         int mx = (i - 1 + k) / (k + 1), mn = (i - 1) / (k + 1);
  20.         res = max(res, (b[n] - b[i - 1]) * mx + curr + sum);
  21.         sum -= (b[n] - b[i]);
  22.         curr += 1LL * mn * a[i];
  23.     }
  24.     res = max(res, curr);
  25.     cout << res << endl;
  26.     return 0;
  27. }