Codeforces-Round-974-Div-3

Lazy_boy_2024-08-222025-03-31

A. Robin Helps

题目描述

There is a little bit of the outlaw in everyone, and a little bit of the hero too. The heroic outlaw Robin Hood is famous for taking from the rich and giving to the poor. Robin encounters n people starting from the 1\-st and ending with the n\-th. The i\-th person has ai gold. If ai≥k, Robin will take all ai gold, and if ai\=0, Robin will give 1 gold if he has any. Robin starts with 0 gold. Find out how many people Robin gives gold to.

给定 $n$ 和 $k$ ,和一个长度为 $n$ 的数组 $a$ ,金币初始值为 0 当 $a_{i} \ge k$ 时,会将 $a_{i}$ 全部取走(即金币数+$a_{i}$), 若 $a_{i}=0$ 并且金币数不为 0 那么会给他一个金币,问最后给了多少人金币?

解题思路

其实只需要将过程模拟下即可

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n);
  for(int i = 0; i < n; i++) std::cin >> a[i];
  int s = 0, cnt = 0;
  for(int i = 0; i < n; i++) {
    if (a[i] >= k) {
      s += a[i];
    }
    if (a[i] == 0 && s) {
      s -= 1;
      cnt++;
    }
  }

  std::cout << cnt << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

B. Robin Hood and the Major Oak

Robin Hood and the Major Oak

题目描述

In Sherwood, the trees are our shelter, and we are all children of the forest.

The Major Oak in Sherwood is known for its majestic foliage, which provided shelter to Robin Hood and his band of merry men and women.

The Major Oak grows ii new leaves in the i-th year. It starts with 1 leaf in year 1.

Leaves last for k years on the tree. In other words, leaves grown in year i last between years i and i+k−1 inclusive.

Robin considers even numbers lucky. Help Robin determine whether the Major Oak will have an even number of leaves in year n.

大橡树在第(i)年会长出两片新叶。第 1 年开始长 1 片叶子。

树叶在树上可以存活 k 年。换句话说，第 i 年长出的树叶在第 i 年和第 i+k-1 年(包括第 i+k-1 年)之间持续生长。

罗宾认为偶数是幸运数字。请帮助罗宾判断这棵橡树在第 n 年的叶子数是否为偶数。

==数据范围:==

$$
1 \le n \le 10^{9}, 1 \le k \le n
$$

解题思路

由于一片树叶的存活期为 $k$ 我们不妨只看后面 $k$ 年的树叶, 对于第 $i$ 年的树叶数量为 $i^ {i}$ ,但是数据范围较大,容易 TLE 或者是爆 longlong ,怎么办呢? 我们可以观察出一个性质: 相同奇偶性的底数和指数的结果奇偶性不变,那么就可以将这个问题化解为 $[n-k+1, n]$ 这个区间的所有数的和

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, k;
  std::cin >> n >> k;
  int l = n - k + 1, r = n;
  int s = (l + r) * k / 2;
  if (s & 1) std::cout << "NO" << endl;
  else std::cout << "YES" << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}

C. Robin Hood in Town

Robin Hood in Town

题目描述

There are n people living in the town. Just now, the wealth of the i-th person was ai gold. But guess what? The richest person has found an extra pot of gold!

More formally, find an aj**=max(a1**,a2**,…,an**), change aj to aj**+**x, where x is a non-negative integer number of gold found in the pot. If there are multiple maxima, it can be any one of them.

A person is unhappy if their wealth is strictly less than half of the average wealth∗.

If strictly more than half of the total population n are unhappy, Robin Hood will appear by popular demand.

Determine the minimum value of x for Robin Hood to appear, or output −1 if it is impossible.

给定长度为 $n$ 的数组 $a$ ,现在要将数 $x$ 加在数组中的最大值上,使得整个数组中小于平均值的一半的数目大于 $\frac{n}{2}$ ,问数 $x$ 的最小值为多少?

解题思路

打眼一看,二分没问题了
已知是将 $x$ 加在最大值上,那么我们可以将数组进行排序,为了使得满足条件 $a_{i}<\frac{\sum_{i=1}^{n}a_{i}}{n2}$ 的数目大于 $\frac{n}{2}$ 那么就只需要在排序好的数组中找到前 $\frac{n}{2}$ 个最小值,只要这其中的最大值都比 $\frac{\sum_{i=1}^{n}a_{i}}{n2}$ 小,就可以满足条件.

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n, s = 0;
  std::cin >> n;
  std::vector<int> a(n);
  for(int i = 0; i < n; i++) std::cin >> a[i], s += a[i];
  if (n <= 2) {
    std::cout << -1 << endl;
    return;
  }
  std::sort(a.begin(), a.end());
  std::function<bool(int)> check = ([&](int x) -> bool {
    int cnt = 0;
    double t = (s + x * 1.0 ) / (n * 2);
    return a[n / 2] < t;
  });

  int l = 0, r = 1e16;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  std::cout << l << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}