17-比赛1 D - IPC Trainers （贪心 + 优先队列）

题目描述

本次印度编程训练营（Indian Programming Camp，IPC）共请到了 N 名教练。训练营的日
程安排有 M 天，每天最多上一节课。第 i 名教练在第 Di 天到达，直到训练营结束才离开。第 i 名
教练希望上 Ti 节课。要是少上了课，那么教练会感到扎心，每少上一节，扎心值就会加 Si。
作为主办方，你希望最小化所有教练的扎心值之和。

数据范围

1 ≤ T ≤ 10
• 1 ≤ N, D, Si ≤ 1e5
• 1 ≤ Di
, Ti ≤ D

输入格式

输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含两个整数 N 和 M。接下来 N 行，每行包含三个整数 Di, Ti, Si。

输出格式

对于每组数据，输出一行，包含一个整数，代表扎心值之和的最小值。

样例输入

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

=====================================================================================================================================

比赛时未做出的题目

学长的题解：

贪心的想每一天让扎心值最大的教练上课 ，所以需要一个数据结构支持查询最大值，插入元素，删除最大值。

优先队列priority_queue可以完美实现这些要求。

=====================================================================================================================================

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node{
   int beg,day,s;
}node[N];
bool operator<(Node a,Node b){ //通过这个方法，自定义优先队列的顺序
    return a.s < b.s;
}
priority_queue<Node> que;
bool cmp(Node a,Node b){
      return a.beg < b.beg;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,D;
        scanf("%d %d",&n,&D);
        for(int i = 1; i <= n; ++i) scanf("%d %d %d",&node[i].beg,&node[i].day,&node[i].s);
        sort(node+1,node+n+1,cmp);
        int now = 1;
        //从每一天开始，每一天优先让能在这一天上课的扎心值最高的教师上课
        for(int i = 1; i <= D; ++i){ 
            //将能在第i天上课的教师加入优先队列
            while(now <= n && node[now].beg == i) que.push(node[now]),++now;  
            //加入完毕之后，让扎心值最高的教师上这一天的课
            if(!que.empty()){
                Node temp;
                temp = que.top();
                que.pop();
                --temp.day; //这位老师想要上的天数-1
                if(temp.day) que.push(temp);
            }
        }
        long long sum = 0;
        //遍历优先队列
        while(!que.empty()) sum += (long long)que.top().day*que.top().s,que.pop();
        printf("%lld\n",sum);
    }
}