pku 2051 stl heap的使用.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;

//PKU 2051 STL Heap的使用
#define NMAX 1050
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back
typedef struct oopmes
{
	int ID;
	int t;
	int dis;
}oopmes;

vector <oopmes> mes;
oopmes mao[NMAX];

bool cmp(oopmes a,oopmes b)
{
	return a.t>b.t || ( a.t==b.t && a.ID >b.ID);
}

void solve(int num,int totle)
{
 int i;
 oopmes temp;
 for(i=1;i<=totle;i++) mes.push_back(mao[i]);
 MH(mes.begin(),mes.end(),cmp);
 for(i=1;i<=num;i++)
 {
	 temp=mes.front();
	 printf("%d\n",temp.ID);
	 OH(mes.begin(),mes.end(),cmp);
	 mes.OB();
	 temp.t+=temp.dis;
	 mes.PB(temp);
	 PH(mes.begin(),mes.end(),cmp);
 }
}

int main()
{
	int i,num,totle;
	char sen[20];
	i=0;
	while(scanf("%s",sen)!=EOF)
	{
		if(sen[0]=='#') break;
		else 
		{
			i++;
			scanf("%d %d",&mao[i].ID,&mao[i].dis);
			mao[i].t=mao[i].dis;
		}
	}
	totle=i;
	scanf("%d",&num);
	solve(num,totle);
	return 0;
}