這題實際上是考察了堆的插入與刪除操作，用到的是大頂堆
有人用二分過的此題，我覺得二分的邊界處理應該比較麻煩吧，尤其如果數據中出現有分數相同的，確實不好處理
比較直觀的思想就是堆了。
我們首先按照分數來進行排序，排序後進行枚舉，對枚舉的每個位置，看該位置之前最小的n/2個需求與該位置之後的最小的n/2個需求的和是否滿足要求。
實際上預先處理一下就可以了，先從頭到尾進行掃，將每個位置的元素插入大頂堆中，如果個數不夠n/2個直接插入，夠了的話，就看根元素是否需要更新。
同理從尾掃到頭。 這樣就預處理了每個位置上之前最小的n/2個元素的和，之後的最小的n/2個元素的和
[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 111111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct node
{
int score, need;
}p[MAXN];
int n, c, f, r, sum;
int high[MAXN], low[MAXN];
bool cmp(node x, node y)
{
return x.score < y.score;
}
int h[MAXN];
void up(int i)
{
int j;
while(i > 1)
{
j = i / 2;
if(h[i] > h[j]) swap(h[i], h[j]);
else break;
i = j;
}
}
void down(int i)
{
int j; www.2cto.com
while(i * 2 <= r)
{
j = i * 2;
if(j + 1 <= r && h[j + 1] > h[j]) j++;
if(h[j] > h[i]) swap(h[i], h[j]);
else break;
i = j;
}
}
void del(int x)
{
sum = sum + x - h[1];
h[1] = x;
down(1);
}
void insert(int x)
{
h[++r] = x;
sum += x;
up(r);
}
int main()
{
scanf("%d%d%d", &n, &c, &f);
for(int i = 1; i <= c; i++) scanf("%d%d", &p[i].score, &p[i].need);
memset(h, 0, sizeof(h));
r = sum = 0;
sort(p + 1, p + c + 1, cmp);
n /= 2;
for(int i = 1; i <= n; i++) insert(p[i].need);
low[n] = sum;
for(int i = n + 1; i <= c - n; i++)
{
if(p[i].need < h[1]) del(p[i].need);
low[i] = sum;
}
memset(h, 0, sizeof(h));
r = sum = 0;
for(int i = c; i > c - n; i--) insert(p[i].need);
high[c - n + 1] = sum;
for(int i = c - n; i > n; i--)
{
if(p[i].need < h[1]) del(p[i].need);
high[i] = sum;
}
int ans = -1;
for(int i = c - n; i > n; i--)
if(low[i - 1] + high[i + 1] + p[i].need <= f)
{
ans = p[i].score;
break;
}
printf("%d\n", ans);
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 111111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct node
{
int score, need;
}p[MAXN];
int n, c, f, r, sum;
int high[MAXN], low[MAXN];
bool cmp(node x, node y)
{
return x.score < y.score;
}
int h[MAXN];
void up(int i)
{
int j;
while(i > 1)
{
j = i / 2;
if(h[i] > h[j]) swap(h[i], h[j]);
else break;
i = j;
}
}
void down(int i)
{
int j;
while(i * 2 <= r)
{
j = i * 2;
if(j + 1 <= r && h[j + 1] > h[j]) j++;
if(h[j] > h[i]) swap(h[i], h[j]);
else break;
i = j;
}
}
void del(int x)
{
sum = sum + x - h[1];
h[1] = x;
down(1);
}
void insert(int x)
{
h[++r] = x;
sum += x;
up(r);
}
int main()
{
scanf("%d%d%d", &n, &c, &f);
for(int i = 1; i <= c; i++) scanf("%d%d", &p[i].score, &p[i].need);
memset(h, 0, sizeof(h));
r = sum = 0;
sort(p + 1, p + c + 1, cmp);
n /= 2;
for(int i = 1; i <= n; i++) insert(p[i].need);
low[n] = sum;
for(int i = n + 1; i <= c - n; i++)
{
if(p[i].need < h[1]) del(p[i].need);
low[i] = sum;
}
memset(h, 0, sizeof(h));
r = sum = 0;
for(int i = c; i > c - n; i--) insert(p[i].need);
high[c - n + 1] = sum;
for(int i = c - n; i > n; i--)
{
if(p[i].need < h[1]) del(p[i].need);
high[i] = sum;
}
int ans = -1;
for(int i = c - n; i > n; i--)
if(low[i - 1] + high[i + 1] + p[i].need <= f)
{
ans = p[i].score;
break;
}
printf("%d\n", ans);
return 0;
}
