题目链接：http://codeforces.com/problemset/problem/1251/D
给你n个区间，让你从中选出n个数使得，总和加起来不超过m并且中位数最大，求最大的中位数。
当时我自作聪明，判断写在清空的上面写凉了，还是不够精细。
ac代码：
#include<set> #include <cstdio> #include <queue> #include <algorithm> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const ll mx=4e5+10; const ll mod=1e9+7; struct node { ll a, b; bool operator<(const node &t) const { return a>t.a; } }s[mx]; ll q, n, m; bool cmp(ll a) { ll sum = 0, ts = n/2+1; for (int i = 0; i < n; ++i) { if (s[i].b < a || !ts) { sum += s[i].a; continue; } sum += max(s[i].a, a); ts--; } if (ts) return false; if (sum <= m) return true; return false; } void solve() { ll l = 0, r = m, ans = 0; while (l <= r) { ll mid = (l+r)>>1; if (cmp(mid)) { ans = mid; l = mid+1; } else r = mid-1; } printf("%lld\n", ans); return; } int main() { scanf("%lld", &q); for (int i = 0; i < q; ++i) { scanf("%lld%lld", &n, &m); for (int j = 0; j < n; ++j) scanf("%lld%lld", &s[j].a, &s[j].b); sort(s, s+n); solve(); } return 0; }wa的代码：
#include<set> #include <cstdio> #include <queue> #include <algorithm> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const ll mx=4e5+10; const ll mod=1e9+7; struct node { ll a, b; bool operator<(const node &t) const { return a>t.a; } }s[mx]; ll q, n, m; bool vis[mx]; bool cmp(ll a) { ll sum = 0, ts = 0; for (int i = 0; i < n; ++i) { if (s[i].b < a) continue; sum += max(s[i].a, a); vis[i] = true; ts++; if (n/2+1 == ts) break; } if (ts != n/2+1) return false;///就是这里写在下面for的下面就行 for (int i = 0; i < n; ++i) { if(vis[i]) { vis[i] = 0; continue; } sum += s[i].a; } if (sum <= m) return true; return false; } void solve() { ll l = 0, r = m, ans = 0; while (l <= r) { ll mid = (l+r)>>1; if (cmp(mid)) { ans = mid; l = mid+1; } else r = mid-1; } printf("%lld\n", ans); return; } int main() { scanf("%lld", &q); for (int i = 0; i < q; ++i) { scanf("%lld%lld", &n, &m); for (int j = 0; j < n; ++j) scanf("%lld%lld", &s[j].a, &s[j].b); sort(s, s+n); solve(); } return 0; }
