[codechef July Challenge 2017] IPC Trainers

IPCTRAIN: 训练营教练
题目描述
本次印度编程训练营（Indian Programming Camp，IPC）共请到了 N 名教练。训练营的日
程安排有 M 天，每天最多上一节课。第 i 名教练在第 Di 天到达，直到训练营结束才离开。第 i 名
教练希望上 Ti 节课。要是少上了课，那么教练会感到扎心，每少上一节，扎心值就会加 Si。
作为主办方，你希望最小化所有教练的扎心值之和。
输入格式
输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含两个整数 N 和 D。接下来 N 行，每行包含三个整数 Di
, Ti
, Si。
输出格式
对于每组数据，输出一行，包含一个整数，代表扎心值之和的最小值。
数据范围和子任务
• 1 ≤ T ≤ 10
• 1 ≤ N, D, Si ≤ 105
• 1 ≤ Di
, Ti ≤ D
子任务 1（40 分）：
• 1 leqN, D, Si ≤ 103
子任务 2（60 分）：
• 无附加限制
样例数据
输入
3
2 3
1 2 300
2 2 100
2 3
1 1 100
2 2 300
2 3
3 2 150
1 1 200
输出
100
0
150
样例解释
对于第一组数据，两名教练都想上两节课，分别在第 1 和第 2 天到达。可以安排第一名教练
上头两天的课程，第二名教练上最后一天的课程。这样第二名教练少上了一节课，扎心程度为
100。可以证明不存在更好的排课方案。
对于第二组数据，可以让所有教练都满意。
对于第三组数据，第一名教练第三天才到，却想上两节课。一天一节课，训练营就三天，所
以只能让他扎心。第二名教练第一天就到了，但只想上一节课，所以可以给他安排第 1 天或者第 2
天。但无论如何，总有一天没有课上。

这题还是比较水的。当然是一个贪心的想法。在某一天，很多人会要求上课。那怎么办？挑代价最大的呗，之后一直都挑代价最大的（且需要能取，没有取完），最后就能得到最优解。那么想到了这里，我们自然会有一个用堆维护的想法。每一天从堆里面挑出最大的一个，那么这个教授需要要求上课的天数少了一天。如果某个教授要求天数变为了0，那么他就没事了。

 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<iostream>
 using namespace std;
 ];
 long long ans;
 struct per{
     int arr,cla,unh;
     bool operator < (const per &other) const {return arr<other.arr;}
 }a[];
 inline int read(){
     ; char ch=getchar();
     ') ch=getchar();
     +ch-',ch=getchar();
     return x;
 }
 void put(int x){
     heap[++len]=x;
     ; son>>=)
     ]].unh&&a[heap[son]].unh>a[heap[son>>]].unh) swap(heap[son],heap[son>>]);
     else break;
 }
 void get(){
     heap[]=heap[len],heap[len]=,len--;
     ; (fa<<)<=n;){
         int son;
         ]].unh>a[heap[fa<<|]].unh||(fa<<|)>n) son=fa<<; |;
         if (a[heap[son]].unh>a[heap[fa]].unh) swap(heap[son],heap[fa]),fa=son;
         else return;
     }
 }
 int main(){
     for (int Ts=read(); Ts; Ts--){
         n=read(),D=read(),ans=len=;
         memset(a,,sizeof a);
         memset(heap,,sizeof heap);
         ; i<=n; i++) a[i].arr=read(),a[i].cla=read(),a[i].unh=read();
         sort(a+,a++n);
         ;
         ; days<=D; days++){
             while (j<=n&&a[j].arr==days) put(j),j++;
             if (!len) continue;
             ]; a[x].cla--;
             if (!a[x].cla) get();
         }
         ; i<=n; i++) ans+=(long long)a[i].unh*a[i].cla;
         printf("%lld\n",ans);
     }
     ;
 }

巴特西

[codechef July Challenge 2017] IPC Trainers

最新文章

热门文章