2013
12-23

# 看病要排队

1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)

7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

2
EMPTY
3
1
1

#include <iostream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;

class hospital
{
public:
int level;
int id;
friend bool operator < (hospital c1,hospital c2)
{
if(c1.level!=c2.level)
return c1.level<c2.level;
else
return c1.id>c2.id;
}
};

int main()
{
int testcase;
while(cin>>testcase)
{
int doc,level;
int as=0;
string op;
priority_queue<hospital> p[4];
hospital tmp;
while(testcase--)
{
cin>>op;
if(op=="IN")
{
as++;
cin>>doc>>level;
tmp.level=level;
tmp.id=as;
//cout<<"idis"<<tmp.id<<endl;
p[doc].push(tmp);

}
else if(op=="OUT")
{
cin>>doc;
if(p[doc].empty())
cout<<"EMPTY"<<endl;
else
{
tmp=p[doc].top();
p[doc].pop();
cout<<tmp.id<<endl;

}
}
}

}
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}