pku2010.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct 
{
	int p, f;
} Cow;

Cow c[100001];
int Heap[10001];
int N, C, F, HeapSize;
int down[100001];

int cp(const void *a, const void *b)
{
	Cow *aa = (Cow *)a;
	Cow *bb = (Cow *)b;
	return bb->p - aa->p;
}

void Swap(int *a, int *b)
{
	int t;
	t = *a;
	*a = *b;
	*b = t;
}

void ReCheck(int pos)
{
	while (pos * 2 <= HeapSize)
	{
		if (pos * 2 + 1 > HeapSize)
		{
			if (Heap[pos] < Heap[pos * 2])
			{
				Swap(&Heap[pos], &Heap[pos * 2]);
			}
			else
			{
				break;
			}
		}
		else
		{
			if (Heap[pos * 2] > Heap[pos * 2 + 1])
			{
				if (Heap[pos] < Heap[pos * 2])
				{
					Swap(Heap + pos, Heap + pos * 2);
					pos = pos * 2;
				}
				else
				{
					break;
				}
			}
			else
			{
				if (Heap[pos] < Heap[pos * 2 + 1])
				{
					Swap(Heap + pos, Heap + pos * 2 + 1);
					pos = pos * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	}
}

void CreateHeap()
{
	int i, pos, tmp;
	for (i = HeapSize >> 1; i > 0; i--)
	{
		ReCheck(i);
	}
}

void Solve()
{
	int i, sum;
	HeapSize = N >> 1;
	for (i = 0; i < C; i++)
	{
		scanf("%d %d", &c[i].p, &c[i].f);
	}
	qsort(c, C, sizeof(c[0]), cp);
	for (i = 1, sum = 0; i <= HeapSize; i++)
	{
		Heap[i] = c[C - i].f;
		sum += Heap[i];
	}
	CreateHeap();
	down[C - HeapSize] = sum;
	for (i = C - HeapSize - 1; i > HeapSize; i--)
	{
		if (c[i].f < Heap[1])
		{
			sum = sum - Heap[1] + c[i].f;
			Heap[1] = c[i].f;
			ReCheck(1);
		}
		down[i] = sum;
	}

	for (i = 1, sum = 0; i <= HeapSize; i++)
	{
		Heap[i] = c[i - 1].f;
		sum += Heap[i];
	}
	CreateHeap();
	for (i = HeapSize; i < C - HeapSize; i++)
	{
		if (sum + c[i].f + down[i + 1] <= F)
		{
			printf("%d\n", c[i].p);
			break;
		}
		if (c[i].f < Heap[1])
		{
			sum = sum - Heap[1] + c[i].f;
			Heap[1] = c[i].f;
			ReCheck(1);
		}
	}
	if (i == C - HeapSize)
	{
		printf("-1\n");
	}
}

int main()
{
	while (scanf("%d %d %d", &N, &C, &F) != -1)
	{
		Solve();
	}
	return 0;
}