CCF-201709-2
我们先来看一下题目解题思路代码优先队列priority_queue的API
我们先来看一下题目
解题思路
你不要看着题目这样，好像要考虑很多东西，优先队列就是干这个的，给个排序规则自动排序，而这个题我们要对时间排序，先来后到，然后还取，先还都取，同时还，小号先还。 优先队列，冲!
代码
#include<iostream>
#include<queue>
using namespace std
;
struct node
{
char op
;
int time
;
int num
;
bool operator <(const node a
)const{
if(a
.time
!=time
) return a
.time
<time
;
else if(a
.op
!=op
) return a
.op
>op
;
else return a
.num
<num
;
}
};
const int maxn
=1000;
int ans
[maxn
+1];
int main(){
priority_queue
<node
> q
;
node t
;
int n
,k
;
cin
>>n
>>k
;
for(int i
=0;i
<=n
;i
++){
ans
[i
]=i
;
}
while(k
--){
int w
,s
,c
;
cin
>>w
>>s
>>c
;
t
.op
='G';
t
.num
=w
;
t
.time
=s
;
q
.push(t
);
t
.op
='R';
t
.time
=s
+c
;
q
.push(t
);
}
while(!q
.empty()){
t
=q
.top();
q
.pop();
if(t
.op
=='G'){
for(int i
=1;i
<=n
;i
++){
if(ans
[i
]==t
.num
) {
ans
[i
]=0;break;
}
}
}else{
for(int i
=1;i
<=n
;i
++){
if(ans
[i
]==0){
ans
[i
]=t
.num
;break;
}
}
}
}
for(int i
=1;i
<=n
;i
++)
cout
<<ans
[i
]<<" ";
return 0;
}
优先队列priority_queue的API
