UVA 10125 Sumsets——折半查找

UVA 10125 Sumsets——折半查找

水题

#include #include #include #include using namespace std;const int maxn = 1e6 + 10;int n, m, a[1005], b[maxn], x[maxn], y[maxn];struct Date { int val, a, b; bool operator < (const Date &d) const { return val < d.val; }}date[maxn];int main() { while (~scanf("%d", &n) && n) { for (int i = 0; i < n; i++) scanf("%d", &a[i]); m = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { date[m].val = a[i] + a[j]; date[m].a = a[i]; date[m].b = a[j]; m++; } } sort(date, date + m); for (int i = 0; i < m; i++) { b[i] = date[i].val; x[i] = date[i].a; y[i] = date[i].b; } int ans = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; int t = a[i] - a[j]; int pos = lower_bound(b, b + m, t) - b; for (int k = pos; k < m && b[k] == t; k++) { if (a[i] != x[k] && a[i] != y[k] && a[j] != x[k] && a[j] != y[k]) { ans = max(ans, a[i]); j = n; break; } } } } if (ans == -1) printf("no solution\n"); else printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。