题解：AT_abc362_c [ABC362C] Sum = 0 - Block

很好写（15 min 解决）但不好讲（跟别人讲了 20 min）的写法 QwQ……

首先，咱先算出原式的范围。最小值（暂且记为 $k$ ）的公式就是：

k = \sum_{i = 1}^{N} L_i

就是每一个最小可能值的和。

同理，最大值（我记为 $w$ ）的公式就是：

w= \sum_{i = 1}^{N} R_i

即最大可能值的和。

算这玩意儿有啥用呢？卡区间！

你说要是 $k > 0$ 或者 $w < 0$ ，即最小都比 $0$ 大或者最大都不到还能干成 $0$ 吗？肯定不能啊！这种情况就是 No。

剩下的鉴于大家都是整数，而且可以随便变化，一定是 Yes（注：其实这就是零点存在定理：当一个函数 f 在 $x \sim y$ 是连续时，如果 $f(x) < 0$ 但 $f(y) > 0$ ，那么一定有 $x < z < y$ 满足 $f(z) = 0$ ）。

所以该咋构造呢？

我们可以以 $k$ 为基准，往 $0$ 去凑。

具体来讲，就是：

Ans_i = \begin{cases}R_i \ (left > R_i - L_i) \\ L_i + left \ (R_i \ge left + L_i)\end{cases}

其中 $left$ 表示到 $0$ 的距离，也就是 $0 - k$ 。~~说人话~~翻译一下就是：

能够直接凑完，那就直接凑完，然后就不用凑了。
凑不完，能凑多少是多少，记得更新一下后面要凑的数目

比如样例 $1$ :

经计算， $left = 3$ ，第一组（ $3 \sim 5$ ）最多凑个 $2$ ，那就凑 $2$ ，输出 $5$ ，还剩个 $1$ 要凑。第二组（ $-4 \sim 1$ ）最多能凑个 $5$ ，但 $1$ 就够了，输出 $-3$ ，不用凑了。最后一组，不用凑了，直接输出 $-2$ 。

算一下， $5 + (-3) + (-2) = 5 - 3 - 2 = 0$ ，满足条件。

注意：今天，你开 long long 了吗？

赛场 AC Code：

1
// Problem: C - Sum = 0
2
// Contest: AtCoder - Toyota Programming Contest 2024#7（AtCoder Beginner Contest 362）
3
// URL: https://atcoder.jp/contests/abc362/tasks/abc362_c
4
// Memory Limit: 1024 MB
5
// Time Limit: 2000 ms
6
//
7
// Powered by CP Editor (https://cpeditor.org)
8

9
/*Code by Block_Fish*/
10
#include <bits/stdc++.h>
11

12
#define log printf
13
#define EPS 1e-8
14
#define INF 0x3f3f3f3f
15
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
16
#define IOS                      \
17
  ios::sync_with_stdio(false); \
18
  cin.tie(nullptr);            \
19
  cout.tie(nullptr);
20

21
using namespace std;
22

23
typedef __int128 i128;
24
typedef long long ll;
25
typedef pair<ll, ll> PII;
26

27
const ll N = 2e5 + 10;
28
ll n, l[N], r[N], lft, suml, sumr;
29

30
template <typename T>
31

32
inline T read() {
33
  T sum = 0, fl = 1;
34
  char ch = getchar();
35
  for (; !isdigit(ch); ch = getchar())
36
    if (ch == '-') fl = -1;
37
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
38
  return sum * fl;
39
}
40

41
template <typename T>
42

43
inline void write(T x) {
44
  if (x < 0) {
45
    putchar('-'), write<T>(-x);
46
    return;
47
  }
48
  static T sta[35];
49
  ll top = 0;
50
  do { sta[top++] = x % 10, x /= 10; } while (x);
51
  while (top) putchar(sta[--top] + 48);
52
}
53

54
int main() {
55
  n = read<ll>();
56
  FOR(i, 1, n) l[i] = read<ll>(), r[i] = read<ll>(), suml += l[i], sumr += r[i];
57
  if (!(suml <= 0 && sumr >= 0)) {
58
    cout << "No";
59
    return 0;
60
  }
61
  lft = 0 - suml;   // 到0剩下的距离
62
  cout << "Yes" << endl;
63
  FOR(i, 1, n) {
64
    if (l[i] + lft <= r[i]) {
65
      cout << l[i] + lft << " ";
66
      lft = 0;
67
    } else {
68
      cout << r[i] << " ";
69
      lft -= r[i] - l[i];
70
    }
71
  }
72
  return 0;
73
}

AC 记录～

理解万岁！

音乐

音乐

支持与分享

评论区