题目描述： 题目链接：http://poj.org/PRoblem?id=2785 这个题的意思是给你四个具有相同元素个数的集合，问能否从每个集合里面挑出一个数，使得四个数的和为0，输出一共有多少种组合可以实现。 题目分析 : 这是第二周训练第二场的一个题，从前做过这个题，可惜当时没有想起来怎么做，总是超时==；这个题可以求出前两个集合的所有和的情况存到一个数组里面，然后对这个数组进行排序。然后再用后两个集合求和，每求出一个和就用lower_bound()和upper_bound 函数在数组中寻找。这道题考的就是这两个函数的用法，可惜我没有想起来怎么用TAT。 复习一下两个函数用法：
此函数详细用法见这篇博文：http://blog.csdn.net/u013475704/article/details/46458723
给出代码：
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>using namespace std;int num[11];int sum1[16000010];int main(){ int n; while(scanf("%d",&n)!=EOF) { int num1[4010],num2[4010],num3[4010],num4[4010]; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&num1[i],&num2[i],&num3[i],&num4[i]); } //int sum1[16000000]; int k=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) sum1[k++]=num1[i]+num2[j]; sort(sum1,sum1+k); int sum=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { int cnt=num3[i]+num4[j]; int pos1=lower_bound(sum1,sum1+k,-cnt)-sum1; int pos2=upper_bound(sum1,sum1+k,-cnt)-sum1; if(sum1[pos1]==-cnt) sum+=(pos2-pos1); } cout<<sum<<endl; } return 0;}新闻热点
疑难解答
