Petya’s Exams
截图：
题意：现在，有n天，m场考试编号1～m，每场考试给出 s 题库发布的时间（即代表从此时起可以开始复习这门科目）d 这门科目考试的时间，t 需要复习的时间。现在，每天你可以选择复习，或者休息，只能选其中一样！如果是考试的时间，则必须去考试！问，你是否可以复习完所有科目并通过考试，如果可以，输出安排表，1～m代表复习功课，0表示休息，m+1表示考试。如果不能，输出-1/。
题解：优先选择考试结束时间早的科目先复习，结构体存储考试题库发放时间，考试时间，考试准备所需时间，以及考试的场次（1~m)，然后建立长度为n的数组存放现有天数时间安排表，把所有给出的考试按照考试时间前后排序，然后把时间安排表中有考试的先安排考试，没有考试的安排复习，从第一天开始安排，之后遇到有考试的直接跳过，并且题库发放时间在第i天之前，考试时间在其之后，则可以安排复习，安排之后，该场考试复习所需时间–，安排好本天，跳出；所有考试和复习安排完以后，则安排休息；安排完所有天数之后判断复习所需时间是否有剩余，有剩余表示复习不完的，输出-1.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=110;
struct node{
int st,ed;
int num,id;
node(){}
node(int _st,int _ed,int _num,int _id):st(_st),ed(_ed),num(_num),id(_id){};
bool operator<(const node& b)const{
if(st==b.st)return ed<b.ed;
return st<b.st;
}
}p[maxn];
int ans[maxn],vis[maxn];
struct pnode{
int ed,num,id;
pnode(){}
pnode(int _ed,int _num,int _id):ed(_ed),num(_num),id(_id){}
bool operator<(const pnode& b)const{
return ed>b.ed;
}
};
priority_queue<pnode> q;
int inq[maxn];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int s,d,c;
scanf("%d %d %d",&s,&d,&c);
ans[d]=i;
p[i]=node(s,d,c,i);
}
sort(p+1,p+m+1);
int wrong=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int id=p[j].id;
if(inq[id])continue;
if(i>=p[j].st){
inq[id]=1;
q.push(pnode(p[j].ed,p[j].num,p[j].id));
}
}
if(ans[i]){
if(!vis[ans[i]]){
wrong=1;break;
}
else
ans[i]=m+1;
}
else{
if(q.empty())ans[i]=0;
else{
pnode now=q.top();
q.pop();
now.num--;
ans[i]=now.id;
if(now.num)
q.push(now);
else
vis[now.id]=1;
}
}
// printf("i:%d %d
",i,ans[i]);
}
if(wrong) printf("-1
");
else{
for(int i=1;i<=n;i++){
if(i==1)printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("
");
}
return 0;
}