AT_arc094_c题解

· · 题解

传送门

题目大意：

有两个长度为 n 的数组 A 和 B，他们数据个数和总和均相等。两个人进行如下操作：

第一个人想尽可能的增加操作次数，第二个人想尽可能的减少操作次数。求在最优情况下的操作次数。

思路分析：

首先，对于两个人所选择的数，不管是哪个人先选择，最后一定会使得 A 数组的某个元素为 0。因为两个数组的数据总和相等，若第一个人不能使得某个元素减到 0，那么第二个人肯定能够使另一个元素减到 0。

然后，因为第一个人想最大化操作次数，所以我们需要选择最 "劣" 的情况，即尽量选择那些操作之后不能使得某个元素归零的情况。

考虑如果 B_i \ge A_i，那么第二个人肯定会选择操作 B_i，而第一个人可以选择 A_i 或者 A_j(j \neq i) 中的任意一个进行操作，所以这种情况不会对最终答案产生影响。

而当 B_i < A_i 时，显然操作 A_i 不能使得 A_i 归零，因为有

\sum_{i=1}^{n} A_i = \sum_{i=1}^{n} B_i

所以第一个人可以选择 A_i 或者 A_j(j \neq i) 中具有最小代价的那个进行操作，即选择使得剩余的数总和最大的情况。

因此枚举每个 i，如果 B_i < A_i，则记录当前最大值 ans = \max(ans, \sum_{j=1,j\ne i}^{n} A_j)，相当于 ans = \max(ans, b_i)，因为两数组和相等，最终答案即为 ans。

代码实现：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 2;
int n, A[maxn], B[maxn];
ll ans = 0; // A 数组总和
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &A[i], &B[i]);
        ans += A[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (B[i] < A[i]) {
            // 如果 A[i] 不可能减为零，选择操作代价最小的数
            // 即选择其他数之和最大的情况
            ans = max(ans, ans - B[i]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}