首页 > 代码库 > uva1152 - 4 Values whose Sum is 0（枚举，中途相遇法）
uva1152 - 4 Values whose Sum is 0（枚举，中途相遇法）
用中途相遇法的思想来解题。分别枚举两边，和直接暴力枚举四个数组比可以降低时间复杂度。可是我不会写。。。看了紫书作者刘汝佳老师的代码，真是太美了！简单明了，就像看吕钦下的棋一样。我就模仿的写了一下：
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long int#define maxn 4005int T,n,A[maxn],B[maxn],C[maxn],D[maxn],sum[maxn*maxn];int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]); } int c=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { sum[c++]=A[i]+B[j]; } } sort(sum,sum+c); LL ans=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ans+=upper_bound(sum,sum+c,-C[i]-D[j])-lower_bound(sum,sum+c,-C[i]-D[j]); //这一句是全篇的点睛之笔！越想越美妙！ } } printf("%lld\n",ans); if(T) printf("\n"); } //fclose(stdin); //fclose(stdout); return 0;}
uva1152 - 4 Values whose Sum is 0（枚举，中途相遇法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。