hdu 5101 n集合选2个不同集合数使和大于k

时间：2022-04-21 09:24:23

http://acm.hdu.edu.cn/showproblem.php?pid=5101

给n个集合，选择两个来自不同集合的数，加和大于k，问有多少种选择方案。

答案=从所有数中选择的两个加和大于k的数的方案数-在同一个集合中选择的两个加和大于k的数的方案数

而对于同一个集合中选择的两个加和大于k的方案数是可以直接排序然后利用单调性快速统计出来的。

注意upper_bound的应用和ans要使用long long因为10^5*10^5/2超界限了..

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <map>

#include <cstring>

#include <algorithm>

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define clr1(x) memset(x,-1,sizeof(x))

using namespace std;

typedef long long LL;

const int maxn = 1005,maxm = 105;

int p[maxn][maxm],n,k,s[maxn*maxm];

int main()

{

    //cout<<(int)2147483647<<endl;

    int _;RD(_);

    while(_--)

    {

        int cnt = 0;

        LL ans = 0;

        RD2(n,k);

        for(int i = 1;i <= n;++i){

            RD(p[i][0]);

            for(int j = 1;j <= p[i][0];++j){

                RD(p[i][j]);

                s[cnt++] = p[i][j];

            }

        }

        sort(s,s+cnt);

        for(int i = 0;i < cnt;++i){

            ans += (s + cnt - upper_bound(s,s+cnt,k - s[i]));

        }

        for(int i = n;i >= 1;--i){

            sort(p[i]+1,p[i] + p[i][0] + 1);

            for(int j = 1;j <= p[i][0];++j){

                ans -= (p[i] + p[i][0] + 1 - upper_bound(p[i]+1,p[i]+p[i][0]+1,k - p[i][j]));

            }

        }

        printf("%I64d\n",ans/2);

    }

    return 0;

}

相关文章