785

# 题目

## Describe

Given S, a set of integers, find the largest d such that a + b + c = d
where a, b, c, and d are distinct elements of S.

## Input

Several S, each consisting of a line containing an integer 1 ≤ n ≤
1000 indicating the number of elements in S, followed by the elements
of S, one per line. Each element of S is a distinct integer between -
536870912 and +536870911 inclusive. The last line of input contains
‘0’.

## Output

For each S, a single line containing d, or a single line containing ‘no solution’.

5
2
3
5
7
12
5
2
16
64
256
1024
0

12
no solution

# 题解

c 移位

1000 的数据量 O(n2) 的复杂度可以接受

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int maxn = 1005;

struct Node {
int a,b;
int sum;
bool operator < (const int &rhs)const {
return sum < rhs;
}
bool operator < (const Node &rhs)const {
return sum < rhs.sum;
}
};

int n;
int a[maxn];
Node sum[maxn*maxn];

bool Do() {
cin >> n;
if(n == 0)
return false;
int pos = 0;
for(int i = 0;i < n;i++) {
cin >> a[i];
}
sort(a,a + n);
for(int i = 0;i < n;i++)
for(int j = 0;j < i;j++) {
sum[pos].a = j;
sum[pos].b = i;
sum[pos++].sum = a[i] + a[j];
}

sort(sum,sum + pos);
bool flag = true;
int ans;

for(int i = n - 1;i >= 0 && flag;i--)
for(int j = n - 1;j >= 0 && flag;j--) {
int minute = a[i] - a[j];
int it = lower_bound(sum,sum + pos,minute) - sum;
for(it;it < pos;it++) {
if(sum[it].sum != minute)
break;
if(sum[it].b < j && i != j) {
ans = a[i];
flag = false;
break;
}
}
}

if(flag)
cout << "no solution" << endl;
else
cout << ans << endl;

return true;
}

int main() {
while(Do());
return 0;
}

• 点击查看/关闭被识别为广告的评论