题目描述
现有N个任务需要处理，同一时间只能处理一个任务，处理每个任务所需要的时间固定为1。
每个任务都有最晚处理时间限制和积分值，在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。
可用于处理任务的时间有限，请问在有限的时间内，可获得的最多积分。
输入描述
第一行为一个数 N，表示有 N 个任务
1 ≤ N ≤ 100
第二行为一个数 T，表示可用于处理任务的时间
1 ≤ T ≤ 100
接下来 N 行，每行两个空格分隔的整数（SLA 和 V），SLA 表示任务的最晚处理时间，V 表示任务对应的积分。
1 ≤ SLA ≤ 100
0 ≤ V ≤ 100000
输出描述
可获得的最多积分
用例
输入 4
3
1 2
1 3
1 4
1 5
输出 5
说明 虽然有3个单位的时间用于处理任务，可是所有任务在时刻1之后都无效。
所以在第1个时间单位内，选择处理有5个积分的任务。1-3时无任务处理。
输入 4
3
1 2
1 3
1 4
3 5
输出 9
说明
第1个时间单位内，处理任务3，获得4个积分
第2个时间单位内，处理任务4，获得5个积分
第3个时间单位内，无任务可处理
共获得9个积分
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int endTime;
int score;
}WorkOrder;
int cmp(const void *a,const void *b){
return (*(WorkOrder*)a).score-(*(WorkOrder*)b).score;
}
int getResult(int n,int t,WorkOrder *wos){
qsort(wos,n,sizeof(WorkOrder),cmp);
int ans=0;
int curTime=0;
WorkOrder *pq=(WorkOrder*)malloc(t*sizeof(WorkOrder));
int pqSize=0;
for(int i=0;i<n;i++){
int endTime=wos[i].endTime;
int score=wos[i].score;
if(curTime<endTime){//当前时间小于任务最晚完成时间
pq[pqSize++]=wos[i];//加入队列
ans+=score;//加上积分
curTime++;
}else{//当前时间大于等于任务最晚完成时间
int min_score=pq[0].score;//最小积分
int min_index=0;
//找到最小积分
for(int j=1;j<pqSize;j++){
if(pq[j].score<min_score){
min_score=pq[j].score;
min_index=j;//最小积分对应下标
}
}
if(score>min_score){//当前积分大于最小积分
ans+=score-min_score;
pq[min_index]=wos[i];//替换较小积分的任务
}
}
while(pqSize>t){//任务数大于t
int min_score=pq[0].score;
int min_index=0;
for(int j=1;j<pqSize;j++){//找到积分最小任务
if(pq[j].score<min_score){
min_score=pq[j].score;
min_index=j;
}
}
ans-=pq[min_index].score;//减去积分最小的任务
for(int j=min_index;j<pqSize-1;j++)
pq[j]=pq[j+1];
pqSize--;//任务数减少
}
}
free(pq);
return ans;
}
int main()
{
int n,t;
scanf("%d",&n);
scanf("%d",&t);
WorkOrder *wos=(WorkOrder*)malloc(n*sizeof(WorkOrder));
for(int i=0;i<n;i++)
scanf("%d %d",&wos[i].endTime,&wos[i].score);
int res=getResult(n,t,wos);
printf("%d\n",res);
free(wos);
return 0;
}