首页 > 代码库 > 51nod 1090 3个数和为0(排序+二分）
51nod 1090 3个数和为0(排序+二分）
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1090
首先将序列进行排序，然后根据a+b+c=0,c=-a-b,二分查找c，注意判重，即c>b。
时间复杂度O(n*n*logn)。
#include<bits/stdc++.h>using namespace std;int n,a[1005];int find(int x){ int l=0,r=n-1; while(l<=r) { int mid=l+r>>1; if(a[mid]==x) return 1; if(a[mid]<x) l=mid+1; else r=mid-1; } return 0;}main(){ int i,j,t=0,sum; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { sum=-a[i]-a[j]; if(sum<=a[j]) //判重 break; if(find(sum)) { t=1; printf("%d %d %d\n",a[i],a[j],-a[i]-a[j]); } } } if(!t) { printf("No Solution\n"); }}
其他解法：
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>using namespace std;#define ll long long#define N 1005ll a[N];int main(){ ll n; scanf("%I64d",&n); for(ll i=0;i<n;i++) { scanf("%I64d",&a[i]); } sort(a,a+n); bool tag=true; for(ll i=0;i<n&&a[i]<0;i++) { for(ll j=i+1,k=n-1;j<n&&j<k;) { while(a[i]+a[j]+a[k]<0&&j<=k) { j++; } while(a[i]+a[j]+a[k]>0&&k>=j) { k--; } if(j>=k) break; if(a[i]+a[j]+a[k]==0) { printf("%I64d %I64d %I64d\n",a[i],a[j],a[k]); tag=false; j++; k--; } } } if(tag) { printf("No Solution\n"); } return 0;}
51nod 1090 3个数和为0(排序+二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。