POJ 2010 堆 - c++编程基础

这题实际上是考察了堆的插入与删除操作，用到的是大顶堆

有人用二分过的此题，我觉得二分的边界处理应该比较麻烦吧，尤其如果数据中出现有分数相同的，确实不好处理

比较直观的思想就是堆了。

我们首先按照分数来进行排序，排序后进行枚举，对枚举的每个位置，看该位置之前最小的n/2个需求与该位置之后的最小的n/2个需求的和是否满足要求。

实际上预先处理一下就可以了，先从头到尾进行扫，将每个位置的元素插入大顶堆中，如果个数不够n/2个直接插入，够了的话，就看根元素是否需要更新。

同理从尾扫到头。这样就预处理了每个位置上之前最小的n/2个元素的和，之后的最小的n/2个元素的和

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#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
#include
#include
#include
#include
#include
#include
#include
#include
#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;
}