欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

17-比赛1 D - IPC Trainers (贪心 + 优先队列)

程序员文章站 2022-10-04 22:38:31
题目描述 本次印度编程训练营(Indian Programming Camp,IPC)共请到了 N 名教练。训练营的日程安排有 M 天,每天最多上一节课。第 i 名教练在第 Di 天到达,直到训练营结束才离开。第 i 名教练希望上 Ti 节课。要是少上了课,那么教练会感到扎心,每少上一节,扎心值就会 ......

题目描述

本次印度编程训练营(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);
    }
}