4894559_ac_47ms_328k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 82 行

#include<iostream>
using namespace std;
struct re
{
	int id,pe,num;
}q[3500];
int ql;
int compare(re a,re b)
{
	if(a.pe*a.num<b.pe*b.num) return -1;
	else if(a.pe*a.num>b.pe*b.num) return 1;
	else return a.id-b.id;
}
void add(re a)
{
	q[ql]=a;
	int i=ql;ql++;
	int f=(i+1)/2-1;
	while(f>=0)
	{
		if(compare(q[f],q[i])>0)
		{
			re temp=q[f];
			q[f]=q[i];
			q[i]=temp;
			i=f;
			f=(i+1)/2-1;
		}
		else break;
	}
}
void del()
{
	q[0].num++;
	int i=0;
	int child;
	if(compare(q[(i+1)*2-1],q[(i+1)*2])<0)
		child=(i+1)*2-1;
	else child=(i+1)*2;
	while(child<=ql)
	{
		if(compare(q[i],q[child])>0)
		{
			re temp=q[i];
			q[i]=q[child];
			q[child]=temp;
			i=child;
			if(compare(q[(i+1)*2-1],q[(i+1)*2])<0) 
				child=(i+1)*2-1;
			else child=(i+1)*2;
		}
		else break;
	}
}
int main()
{
	int k,id,pe,count;
	char x[100];
	re temp;
	ql=0;
	temp.id=0;temp.pe=3000;temp.num=10000;
	for(count=0;count<3000;count++)
		q[count]=temp;
	cin>>x;
	while(x[0!='#'])
	{
		cin>>id>>pe;
		temp.id=id;
		temp.pe=pe;
		temp.num=1;
		add(temp);
		cin>>x;
	}
	cin>>k;
	for(count=0;count<k;count++)
	{
		temp=q[0];
		cout<<q[0].id<<endl;
		del();
	}
	return 0;
}