题解：AT_abc352_c [ABC352C] Standing On The Shoulders

归档56

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

题解：AT_abc352_c [ABC352C] Standing On The Shoulders

622 字

3 分钟

题解：AT_abc352_c [ABC352C] Standing On The Shoulders

2024-05-04

2026-10-03

AtCoder Beginner Contest

浏览量加载中...

考场憋了很久，最后代码贼短……

理想状态下，直接全排列解决问题。但是， $1 \le n \le 2 \times 10^5$ ，明显 TLE，试都不用试的。

咋优化呢？

其实，前面的巨人只负责“打地基”，作为“塔尖儿”的巨人有且仅有 1 个。而前面地基随便排列，地基高度（他们的和）都不会变。所以，我们只需要枚举塔尖即可。塔尖儿定了，下面的地基高度也就定了。

然后，又是一个问题——求和！理论来讲，最最暴力的方法就是一层循环。但是，一层循环时间复杂度为 $\Theta(n)$ ，联合上枚举塔尖的循环，时间复杂度为 $\Theta(n^2)$ ，又 TM 挂了……

这里，我们可以采用一种类似前缀和的思想：用一个变量 $sum$ （学名叫累加器）来记录 $A$ 的总和，然后算去掉塔尖（ $P_i$ ）的时候，答案就是 $sum - A_{P_i} + B_{P_i}$ 。这个操作，时间复杂度显然为 $\Theta(1)$ ，算上循环为 $\Theta(n)$ ，明显可以。

赛场 ACCode：

1
// Problem: C - Standing On The Shoulders
2
// Contest: AtCoder - AtCoder Beginner Contest 352
3
// URL: https://atcoder.jp/contests/abc352/tasks/abc352_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, mx = -INF, sum1;
29
PII g[N];  // pair 可以把两个数组怼到一块儿，具体使用方法见 https://blog.csdn.net/sevenjoin/article/details/81937695
30

31
template <typename T>
32

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

42
template <typename T>
43

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

55
int main() {
56
  n = read<ll>();  // 不开 long long 见**，别问，问就是实践出来的真知
57
  FOR(i, 1, n) g[i].first = read<ll>(), g[i].second = read<ll>(), sum1 += g[i].first;  // 累加器
58
  FOR(i, 1, n)
59
  mx = max(mx, sum1 - g[i].first + g[i].second);  // 上面简单的公式
60
  write<ll>(mx);
61
  return 0;
62
}