首页 > 代码库 > POJ 2785(4 Values whose Sum is 0)
POJ 2785(4 Values whose Sum is 0)
【题意描述】
对于给定的四个序列,从每个序列中选出一个数,并让四个数相加,输出所有相加和为0的情况数目。
【解题思路】
我们可以考虑前两列的数字相加之和一定与后两列相加和互为相反数,那么我们可以枚举出前两列数字之和,并且,枚举出后两列数据之和的相反数,并对之排序,然后利用二分法进行查找即可。
【AC代码】
#include<iostream>#include<algorithm>using namespace std;int n,ans,a[4040],b[4040],c[4040],d[4040],ab[4040*4040],cd[4040*4040];int main(){ int n; while(cin>>n) { for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i]; int pab=0,pcd=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ab[pab++]=a[i]+b[j]; cd[pcd++]=-(c[i]+d[j]); } } sort(cd,cd+pcd); for(int i=0;i<pab;i++) { int mid,low=0,up=pcd-1; while(low<=up) { mid=(low+up)/2; if(cd[mid]==ab[i]) { ans++; for(int j=mid+1;j<pcd;j++) { if(cd[j]==ab[i]) ans++; else break; } for(int j=mid-1;j>=0;j--) { if(cd[j]==ab[i]) ans++; else break; } break; } else { if(cd[mid]>ab[i]) up=mid-1; else low=mid+1; } } } cout<<ans<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。