本文共 1675 字，大约阅读时间需要 5 分钟。
题意：给你一个集合,每俩个数相加得到一个和s,输入s1,问离s1最近的s是多少
二分,注意如果二分出相等,那一定是最近的数,要不然就比较最后mid和mid-1的数
#include #include #include #include #include #include #include #include namespace cc{ using std::cout; using std::endl; using std::cin; using std::map; using std::vector; using std::string; using std::sort; using std::priority_queue; using std::greater; using std::vector; using std::swap; constexpr int N = 1001; //constexpr int N = 30; //priority_queue , greater >q; int a[N]; int b[N*N]; void solve() { int n; int t = 0; while (cin >> n && n) { t++; for (int i = 0;i < n;++i) cin >> a[i]; int k = 0; for (int i = 0;i < n - 1;i++) { for (int j = i + 1;j < n;j++) { b[k++] = a[i] + a[j]; } } sort(b, b + k); int c, q; cin >> c; cout << "Case " << t << ":" << endl; while (c) { cin >> q; int qq = INT32_MAX; int l = 0, r = k-1; int mid=0; int ok = 0; while (l <= r) { mid = (l + r) / 2; if (b[mid] < q) l = mid + 1; else if (b[mid] > q) r = r - 1; else { ok = 1; break; } } if(ok) cout << "Closest sum to " << q << " is " << q<<"." << endl; else { if(mid==0) cout << "Closest sum to " << q << " is " << b[mid] << "." << endl; else if(abs(b[mid-1]-q) < abs(b[mid]-q)) cout << "Closest sum to " << q << " is " << b[mid-1] << "." << endl; else cout << "Closest sum to " << q << " is " << b[mid] << "." << endl; } --c; } } }};int main(){#ifndef ONLINE_JUDGE freopen("d://1.text", "r", stdin);#endif // !ONLINE_JUDGE cc::solve(); return 0;}
转载于:https://www.cnblogs.com/shuiyonglewodezzzzz/p/9949697.html