題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5101

題意：給定一些集合，選擇兩個來自不同集合的數，加和大于k，問有多少種選擇方案

答案=從所有數中選擇的兩個加和大于k的數的方案數-在同一個集合中選擇的兩個加和大于k的數的方案數

而對于同一個集合中選擇的兩個加和大于k的方案數是可以直接排序然后利用單調性快速統計出來的。

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define LL __int64 using namespace std;int t; int n,k;int main() {scanf("%d",&t);while(t--){vector<int>q[1100];scanf("%d%d",&n,&k);for(int i=1; i<=n; i++){int m;scanf("%d",&m);for(int j=1; j<=m; j++){int x;scanf("%d",&x);q[i].push_back(x);q[0].push_back(x);}sort(q[i].begin(),q[i].end());}sort(q[0].begin(),q[0].end());LL ans=0;for(int i=1; i<=n; i++){for(int j=0; j<(int)q[i].size(); j++){int v=q[i][j];LL num1=q[0].end()-lower_bound(q[0].begin(),q[0].end(),k-v+1);LL num2=q[i].end()-lower_bound(q[i].begin(),q[i].end(),k-v+1);ans+=num1-num2;}}printf("%I64d\n",ans/2);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5101（二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。