昨天做了2008，今天準(zhǔn)備做2009。但是看了下題目，發(fā)現(xiàn)爆難，才100個(gè)人過。
覺得這種題還是別碰了，等以后牛逼了再做。
于是跳過2008年，直接到2010年了！呵呵。
這題還是算容易的，比較適合自己水平發(fā)揮，用堆來做，速度尚可 188ms 。
思路：
先把牛按照score排序一下，然后從后往前找，把每一頭牛當(dāng)做是位于中間的那頭牛。
那現(xiàn)在就是求：
該頭牛前面的所有牛中，哪 (N - 1) / 2 頭牛aid值的和最小。
該頭牛后面的所有牛中，哪 (N - 1) / 2 頭牛aid值的和最小。
這就是典型的用堆可以解決的問題了。
#include <stdio.h>
#include <stdlib.h>
#define MAX_C 100032
#define MAX_N 20032
struct node 
{
int score, aid;
};
struct node in[MAX_C];
int N, C, F;
int after[MAX_C], before[MAX_C];
int heap_size, heap_sum, heap[MAX_N];
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->score - ((struct node *)b)->score;
}
__inline void shift_down(int idx)
{
int val = heap[idx];
while (1) {
idx *= 2;
if (idx > heap_size)
break ;
if (idx + 1 <= heap_size && heap[idx + 1] > heap[idx])
idx++;
if (heap[idx] <= val)
break;
heap[idx / 2] = heap[idx];
}
heap[idx / 2] = val;
}
__inline int heap_init(int start, int len)
{
int i;
heap_sum = 0;
for (i = start; i < start + len; i++) {
heap[i - start + 1] = in[i].aid;
heap_sum += in[i].aid;
}
for (i = heap_size / 2; i >= 1; i--)
shift_down(i);
return heap_sum;
}
__inline int heap_update(int aid)
{
if (aid < heap[1]) {
heap_sum -= heap[1] - aid;
heap[1] = aid;
shift_down(1);
}
return heap_sum;
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &C, &F);
for (i = 0; i < C; i++)
scanf("%d%d", &in[i].score, &in[i].aid);
qsort(in, C, sizeof(in[0]), cmp);
heap_size = (N - 1) / 2;
before[heap_size - 1] = heap_init(0, heap_size);
for (i = heap_size; i < C; i++)
before[i] = heap_update(in[i].aid);
after[C - heap_size] = heap_init(C - heap_size, heap_size);
for (i = C - heap_size - 1; i >= 0; i--)
after[i] = heap_update(in[i].aid);
for (i = C - heap_size - 1; i - heap_size >= 0; i--) {
if (in[i].aid + before[i - 1] + after[i + 1] <= F)
break;
}
printf("%d\n", i - heap_size < 0 ? -1 : in[i].score);
return 0;
}