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 + ;

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 = ; i <= n; ++i) scanf("%d %d %d",&node[i].beg,&node[i].day,&node[i].s);

        sort(node+,node+n+,cmp);

        int now = ;

        //从每一天开始，每一天优先让能在这一天上课的扎心值最高的教师上课

        for(int i = ; 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 = ;

        //遍历优先队列

        while(!que.empty()) sum += (long long)que.top().day*que.top().s,que.pop();

        printf("%lld\n",sum);

    }

}

巴特西

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

最新文章

热门文章