银行门户网站建设,电商运营教程,沈阳网站app制作,赣州招聘网题意#xff1a;
给你N个任务#xff0c;每个任务 iii 都有截止日期DiD_{i}Di和报酬PiP_{i}Pi#xff0c;每完成一个工作需要耗费1的单位时间,你需要使所得报酬最大并输出。
题目描述
Farmer John has so very many jobs to do! In order to run the farm efficientl…题意
给你N个任务每个任务 iii 都有截止日期DiD_{i}Di和报酬PiP_{i}Pi每完成一个工作需要耗费1的单位时间,你需要使所得报酬最大并输出。
题目描述
Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.
His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 N 100,000) jobs
conveniently numbered 1…N for work to do. It is possible but
extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.
Job i has deadline D_i (1 D_i 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 P_i 1,000,000,000).
What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.
输入格式 Line 1: A single integer: N Lines 2…N1: Line i1 contains two space-separated integers: D_i and P_i
输出格式
Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.
题意翻译
约翰的工作日从 0时刻开始有 10910^{9}109个单位时间。在任一单位时间他都可以选择编号1到N 的N(1N105)N(1N10^{5})N(1N105) 项工作中的任意一项工作来完成。工作 iii的截止时间是 Di(1Di109)D_{i}(1D_{i}10^{9})Di(1Di109) 完成后获利是 。在给定的工作利润和截止时间下求约翰能够获得的利润最大为多少。
输入
3 2 10 1 5 1 7
输出
17
说明/提示
Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 10 - 17).
分析
1.先假设如果一个工作有时间去做就先做了它将各项工作按截止时间压入一个小根堆。 2.当我们找到一个没法做却价值比当前堆顶高的工作时我们就放弃那个最小的工作用做它的时间去做这个价值更高的工作。用优先队列小根堆来维护队首元素最小。 3.在判断第 i 项工作做与不做时若其截至时间符合条件则将其与队中报酬最小的元素比较若第 i 项工作报酬较高后悔则 ans a[i].p - q.top()。
复习
C优先队列的基本使用方法 在优先队列中优先级高的元素先出队列。 标准库默认使用元素类型的操作符来确定它们之间的优先级关系。
优先队列的第一种用法也是最常用的用法 priority_queue int q;//通过操作符可知在整数中元素大的优先级高。故队列由大到小通过操作符可知在整数中元素大的优先级高。故队列由大到小
第二种方法 如果我们要把元素从小到大输出怎么办呢 这时我们可以传入一个比较函数使用functional.h函数对象作为比较函数。
priority_queueint,vectorint,greaterintq;其中 第二个参数为容器类型。 第二个参数为比较函数。
第三种方法 自定义优先级直接在结构体里写或者写一个函数
struct node
{int x,y;bool operator(const nodea)const{return xa.x;}
}s[M];AC代码
#includestdio.h
#includestring.h
#includealgorithm
#includeiostream
#includequeue
using namespace std;
typedef long long ll;
const int M1e510;struct node{int x,y;bool operator(const nodea)const{return xa.x;}
}s[M];
priority_queueint,vectorint,greaterint q;// 之前要有空格
int n;
ll ans;
int main(){cinn;ans0;for(int i1;in;i){cins[i].xs[i].y;}sort(s1,sn1);//先对时间排序for(int i1;in;i){if(s[i].xq.size()){//当我们找到一个没法做却价值比当前堆顶高的工作时我们就放弃那个最小的工作用做它的时间去做这个价值更高的工作。if(s[i].yq.top()){//用优先队列小根堆来维护队首元素最小。ansanss[i].y-q.top();q.pop();q.push(s[i].y);}}else{//可以做就直接放进去q.push(s[i].y);anss[i].y;}}coutansendl;return 0;
}
