杜拉拉升职记 巩新亮版 电视剧,dede源码,兰陵缭乱下载
题目描述
本次印度编程训练营（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);
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论