题解：AT_abc365_c [ABC365C] Transportation Expenses

归档56

题解34 未分类7 游寄6 “你需要知道的一切”系列4 博客指南3 网络前端1 闲话1

题解：AT_abc365_c [ABC365C] Transportation Expenses

613 字

3 分钟

题解：AT_abc365_c [ABC365C] Transportation Expenses

2024-08-03

2026-10-27

AtCoder Beginner Contest

浏览量加载中...

Tip

注：为了方便，下文以 $Sum$ 表示 $\sum_{i = 1}^{n} A_i$ 。

$N = 2 \times 10^5$ ，考虑二分答案。

所以，答案有单调性吗？或者说，可以二分吗？

当然！如果 $x = k$ 时可以满足条件，那么 $x = k - 1$ 时显然只会更少（上面取 $\min$ 的基本都没变，变了的取了更少的），一样能满足条件。

$\operatorname{check}$ 函数怎么写？扫一遍嘛，时间复杂度 $O(n)$ ，鉴于后面是 $\log$ 级别的复杂度这里就算暴力扫也超不了。

这样我们只需要考虑二分的上下界就好了。最低直接让 $x = 0$ 好了，最高肯定不会超过 $Sum$ （超了那还了得？多的钱幽灵拿了？），就以此为界二分吧！

等等，我们漏了一个很重要的情况！那就是——无！解！

啥时候可以取到无限啊？

按照题意，需要的钱数最大也只有 $Sum$ 这么多，如果这还不到 $m$ ，即 $Sum \le m$ ，那么 $x$ 自然可以随便取，反正钱数都没它啥事儿……

还有一点，上面这一大堆东西时间复杂度到底是多少呢？

显然时间复杂度为 $\Theta(N \log Sum)$ 。感觉会超？注意时间限制是 2s ！~~拿计算器摁一下~~，最大值（两项都取到最大）大概是 $9.5 \times 10^7$ ，不会超~

然后就真的结束了……

ACCode:

1
/*Code by Block_Fish*/
2
#include <bits/stdc++.h>
3

4
#define INF 0x3f3f3f3f
5
#define EPS 1e-8
6
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
7
#define log printf
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<ll, ll> PII;
18

19
const ll N = 2e5 + 10;
20
ll m, n, a[N], sum;
21

22
template <typename T>
23

24
inline T read() {
25
  T sum = 0, fl = 1;
26
  char ch = getchar();
27
  for (; !isdigit(ch); ch = getchar())
28
    if (ch == '-') fl = -1;
29
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
30
  return sum * fl;
31
}
32

33
template <typename T>
34

35
inline void write(T x) {
36
  if (x < 0) {
37
    putchar('-'), write<T>(-x);
38
    return;
39
  }
40
  static T sta[35];
41
  ll top = 0;
42
  do { sta[top++] = x % 10, x /= 10; } while (x);
43
  while (top) putchar(sta[--top] + 48);
44
}
45

46
inline bool chk(ll q) {
47
  ll sum = 0;
48
  FOR(i, 1, n) {
49
    sum += min(q, a[i]);
50
    if (sum > m) return 0;
51
  }
52
  return sum <= m;
53
}
54

55
int main() {
56
  scanf("%lld%lld", &n, &m);
57
  FOR(i, 1, n) scanf("%lld", &a[i]), sum += a[i];
58
  if (sum <= m) {
59
    log("infinite");
60
    return 0;
61
  }
62
  ll l = 0, r = sum, ret = -1;
63
  while (l <= r) {
64
    ll mid = (l + r) >> 1;
65
    if (chk(mid)) {
66
      ret = mid;
67
      l = mid + 1;
68
    } else r = mid - 1;
69
  }
70
  log("%lld\n", ret);
71
  return 0;
72
}