首页 > 代码库 > hdu 5101 Select
hdu 5101 Select
http://acm.hdu.edu.cn/showproblem.php?pid=5101
在比赛的时候没有想出怎么做，自己真水。
题意：给定一些集合，选择两个来自不同集合的数，加和大于k，问有多少种选择方案。
思路：答案=从所有数中选择的两个加和大于k的数的方案数-在同一个集合中选择的两个加和大于k的数的方案数而对于同一个集合中选择的两个加和大于k的方案数是可以直接排序然后利用单调性快速统计出来的。利用vector把所有的数存到q[0]里面。对q[0]排序，也对q[i]排序。
然后在q[0]找每一个k-v+1的位置，用q.end()减去这个位置就是大于等于这个k-v+1的个数，求出这个个数之后再减去在同一个集合里面的个数就是符合要求，这里的v是存入的数。
求出的ans是答案的二倍，ans/2就是答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #define LL __int64 6 using namespace std; 7 8 int t; 9 int n,k;10 11 int main()12 {13 scanf("%d",&t);14 while(t--)15 {16 vector<int>q[1100];17 scanf("%d%d",&n,&k);18 for(int i=1; i<=n; i++)19 {20 int m;21 scanf("%d",&m);22 for(int j=1; j<=m; j++)23 {24 int x;25 scanf("%d",&x);26 q[i].push_back(x);27 q[0].push_back(x);28 }29 sort(q[i].begin(),q[i].end());30 }31 sort(q[0].begin(),q[0].end());32 LL ans=0;33 for(int i=1; i<=n; i++)34 {35 for(int j=0; j<(int)q[i].size(); j++)36 {37 int v=q[i][j];38 LL num1=q[0].end()-lower_bound(q[0].begin(),q[0].end(),k-v+1);39 LL num2=q[i].end()-lower_bound(q[i].begin(),q[i].end(),k-v+1);40 ans+=num1-num2;41 }42 }43 printf("%I64d\n",ans/2);44 }45 return 0;46 }
hdu 5101 Select
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。