题解：CF421D Bug in Code

· · 题解

CF421D Bug in Code 题解

CF：Link。

1. 思路分析

我们可以用一个数组 a_i 来存储第 i 个鸭鸭被投的票数。

那么，题意就可以转化为：求满足 a_x + a_y \ge P 的无序点对 (x, y) 的数量。

但是，真的是这样吗？

显然，当一个鸭鸭同时投给了 x 和 y 时，贡献会被统计两遍，而题目中说的是鸭鸭的数量，所以我们应该减去一。

因此，我们的题意又可以修改为：求满足 a_x + a_y - cnt(x, y) \ge P 的无序点对 (x,y) 的数量。其中 cnt(x, y) 表示同时投给了 x 和 y 的鸭鸭的数量，我们直接用 map 统计即可，注意是无序的。

但是我们发现这样并不好统计，于是我们可以先统计满足 a_x + a_y \ge P 的点对的数量，再减去同时满足 a_x + a_y \ge P 和 a_x + a_y - cnt(x, y) < P 的点对的数量。

我们可以用双指针统计满足 a_x + a_y \ge P 的点对的数量。

::::info[具体地：]{open}

首先，我们将数组 a 按照升序排序，令排序后的数组为 b。显然，当我们固定 b_i 时，随着另一个指针 j 逐渐增大，b_i + b_j 也会越来越大。因此我们只需要找到一个满足 b_i + b_j \ge P 的最小的 j，那么 j, j + 1, \dots, n 都是满足条件的。

所以，我们定义两个指针 i, j，其中 j 初始为 n。然后，我们从左往右枚举每个 i，同时将 j 不断左移，直到 b_i + b_j < P 或 i = j。此时答案就加上 n - (j + 1) + 1 即 n - j。注意当 j < i 时，要将 j 设为 i。

::::

最后，我们要减去同时满足 a_x + a_y \ge P 和 a_x + a_y - cnt(x, y) < P 的点对的数量。因为我们是用 map 存的 cnt，所以我们可以直接遍历 map，然后再进行判断：如果满足条件，就把答案减一。因为我们只输入了 n 个点对，所以时间复杂度为 O(n)，满足题意。

2. AC 代码

AC 记录。

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
int a[300005], b[300005];
map<pii, int> mp;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[x]++;
        a[y]++;
        if (x > y)
            swap(x, y);
        mp[{x, y}]++;
    }
    for (int i = 1; i <= n; i++) {
        b[i] = a[i];
    }
    int ans = 0;
    sort(b + 1, b + n + 1);
    for (int i = 1, j = n; i <= n; i++) {
        if (i > j)
            j = i;
        while (i < j && b[i] + b[j] >= m) {
            j--;
        }
        ans += n - j;
    }
    for (auto [i, j] : mp) {
        if (a[i.first] + a[i.second] >= m && a[i.first] + a[i.second] - j < m) {
            ans--;
        }
    }
    cout << ans;
    return 0;
}