牛客月赛-分组求对数和

原题链接

题目描述

牛牛幼稚园的小朋友在做游戏。
幼稚园共有 n 个小朋友，第 i 个小朋友有 $s_i$个数字，第 i 个小朋友手中的第 jj 个数字记为 $a_{ij}(1\le j\le s_i)$。
现在牛牛老师想要知道有多少种不同的方式从两个不同的小朋友手中各取一个数字使得数字的和大于等于 k ？
由于可能的方式可能十分多，所以你只需要告诉牛牛这个方案数模 998244353 之后的结果就可以了（同一个小朋友手中相同的数字分别组成的答案看作是不同的）。

输入样例

3 7
4 2 3 1 5
2 4 1
2 8 2

输出样例

9

---

算法

(容斥原理思想 + 二分查找)

本题首先想到的是爆搜枚举，一一枚举搜索所有的相加大于 k 的可能，但这显然会超时，是平方级别的复杂度

所以，我们可以想到，本题 k 已经给出，所以我们只要求出每个数字与 k 的差值更大的数有多少个即可，那么就不难想到先排序然后用二分查找。

由于每个数字查找不能包含本组数字，我们就可以每次查找分两个区间，将大区间查找的数减去小区间中的数，最后累加即是答案。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;const ll mod = 998244353;
    
int main()
{
    ll n,k,cnt;
    cin >> n >> k;
    vector<ll> v[N],all; 
    for (int i = 0;i < n;i ++ ) {
        int m;
        cin >> m;
        for (int j = 0;j < m;j ++ ) {
            int x;
            cin >> x;
            v[i].push_back(x);
            all.push_back(x);
            cnt ++;
        }
        sort(v[i].begin() , v[i].end());
    }
    sort(all.begin(),all.end());
    
    ll res = 0,t1 = 0,t2 = 0;
    for (int i = 0;i < n;i ++ ) {
        for (int j = 0;j < v[i].size();j ++ ) {
            t1 = 0,t2 = 0;
            t1 = lower_bound(v[i].begin(),v[i].end(),k - v[i][j]) - v[i].begin();
            t1 = (ll)v[i].size() - t1;
            t2 = lower_bound(all.begin(),all.end(),k - v[i][j]) - all.begin();
            t2 = cnt - t2;
            //cout << t2 << ' ' << t1 << '\n';
            res = (res + t2 - t1) % mod;
        }
    }
    cout << res / 2 << '\n';
    return 0;
}