2014
03-13

Resource Allocation

HDU-Sailormoon is made up of three girls~~~wj, xq, lff, usually they work together —- solve a variety of problems. So they has to use some resources in the process.
In order to make it more convenient, they will put some resources in a box big enough, each resource has its ID and level of priority. When they want a kind of resources, they will give its ID and get it from the box. If there are several ones available in the box, they will get the highest priority ones. If there are still several ones available, they will get the one which puts in the box first.

The input will consist of several cases, please deal with till the end of file. Each case contains a integer N(0<N<=10000), representing there are N steps following. For example, if input is "R x y"(x, y are integers,0<=x,y<=10000), representing they put a resource to the box, its ID is x, and its priority is y(the higher the priority is, the smaller the y is). If input is "name r" (name may be "wj" or "xq" or "lff", r is an integer,0<=r<=10000), representing one girl called "name" wants a resource, which ID is r.

The input will consist of several cases, please deal with till the end of file. Each case contains a integer N(0<N<=10000), representing there are N steps following. For example, if input is "R x y"(x, y are integers,0<=x,y<=10000), representing they put a resource to the box, its ID is x, and its priority is y(the higher the priority is, the smaller the y is). If input is "name r" (name may be "wj" or "xq" or "lff", r is an integer,0<=r<=10000), representing one girl called "name" wants a resource, which ID is r.

9
R 1 5
R 2 3
R 1 5
R 2 0
wj 1
xq 2
lff 3
lff 2
xq 2

wj gets Num 1: 1 5!
xq gets Num 4: 2 0!
No one fits!
lff gets Num 2: 2 3!
No one fits!

ID好的范围是10000，询问的次数也是10000，里面的hash操作是多余了，自己没有考虑清楚………………

View Code

#include<iostream>
#include<algorithm>
#include<queue>
#define MAXN 10010
using namespace std;
struct node
{
int pri,num;
bool friend operator<(const node a,const node b)
{
if(a.pri!=b.pri)
return a.pri>b.pri;
return a.num>b.num;
}
};
int hash1[MAXN],h;
priority_queue<node> Q[MAXN];
int main()
{
int n,x,y,r,cc;
char str[10];
while(scanf("%d",&n)==1)
{
h=0;
cc=1;
for(int i=0;i<=n;i++)
while(!Q[i].empty())
Q[i].pop();
memset(hash1,-1,sizeof(hash1));

while(n--)
{
node temp;
scanf("%s",str);
if(str[0]=='R')
{
scanf("%d %d",&x,&y);
if(hash1[x]==-1)
hash1[x]=h++;
temp.num=cc++;
temp.pri=y;
Q[hash1[x]].push(temp);
}
else {
scanf("%d",&r);
if(hash1[r]==-1)
hash1[r]==h++;
if(Q[hash1[r]].empty())
printf("No one fits!\n");
else
{
temp = Q[hash1[r]].top();
printf("%s gets Num %d: %d %d!\n",str,temp.num,r,temp.pri);
Q[hash1[r]].pop();
}
}
}
}
return 0;
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。