[51NOD1090] 3个数和为0(水题,二分)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1090

找到所有数的和,然后再原数组里二分找符合条件的第三个数。

 #include <bits/stdc++.h>
using namespace std; const int maxn = ;
const int maxm = maxn * maxn;
typedef struct R {
int x, y, z;
R(){}
R(int x, int y, int z) : x(x), y(y), z(z) {}
bool operator == (R t) {
return x == t.x && y == t.y && z == t.z;
}
}R;
typedef struct S {
int i, j;
int s;
}S; vector<R> ret;
int n, m;
int a[maxn];
S s[maxm]; bool cmp(R a, R b) {
if(a.x == b.x) {
if(a.y == b.y) return a.z < b.z;
return a.y < b.y;
}
return a.x < b.x;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
m = ; ret.clear();
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a+n);
for(int i = ; i < n; i++) {
for(int j = i+; j < n; j++) {
s[m].i = i; s[m].j = j; s[m].s = a[i] + a[j];
m++;
}
}
for(int i = ; i < m; i++) {
int x = -s[i].s;
int id = lower_bound(a, a+n, x) - a;
if(a[id] == x && id != s[i].i && id != s[i].j) {
int x = a[s[i].i], y = a[s[i].j], z = a[id];
if(x > y) swap(x, y);
if(x > z) swap(x, z);
if(y > z) swap(y, z);
ret.push_back(R(x,y,z));
}
}
if(ret.size() == ) {
puts("No Solution");
continue;
}
sort(ret.begin(), ret.end(), cmp);
ret.erase(unique(ret.begin(), ret.end()), ret.end());
for(int i = ; i < ret.size(); i++) {
printf("%d %d %d\n", ret[i].x, ret[i].y, ret[i].z);
}
}
return ;
}
上一篇:shardingJdbc专题系列(五)之Inline策略 java config 实现方式


下一篇:基于Python清除破损图片需求实现