POJ3579 Posted on 2017-03-24 | In Competitive Programming , POJ MedianSolution sketch超棒的題目! 想想這個數列吧! 2 2 3 9 AC Code1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <algorithm>#include <climits>#include <cstdio>using namespace std;typedef long long ll;const int N = 100100;int n, inp[N];// true if median > xll check(int x){ ll ans = 0; for (int i = 0; i < n; i++) { int l = i, r = n; // [l, r) while (r - l > 1) { int mid = (l + r) / 2; if (inp[mid] - inp[i] <= x) l = mid; else r = mid; } // l ans += l - i; } return ans;}int main(){ while (scanf("%d", &n) == 1) { for (int i = 0; i < n; i++) { scanf("%d", &inp[i]); } sort(inp, inp + n); int l = 0, r = inp[n - 1] - inp[0]; ll total = ((ll)n * (n - 1)) / 2; while (r - l > 1) { int mid = l + (r - l) / 2; ll val = check(mid); if (val < (total + 1) / 2) { l = mid; } else { r = mid; } } printf("%d\n", l + (check(l) < (total + 1) / 2)); } return 0;}