贪心-自命题-作业排期

简介: 作业排期 某机器上需要处理n个作业,每个作业都有一个收益值p与完成期限d。每个作业均占时1个时间单位。 请你安排作业,得到最大收益。输入格式 n p0 p1 ... pn (收益值非递减排练) d0 d1 ... dn输出格式 总收益 作业序列(编号从0开始)输入样例 6 90 80 50 30 20 10 1 2 1 3 4 3输出样例 220[0, 1, 3, 4

作业排期

某机器上需要处理n个作业,每个作业都有一个收益值p与完成期限d。每个作业均占时1个时间单位。

请你安排作业,得到最大收益。

输入格式

n
p0 p1 ... pn (收益值非递减排练)
d0 d1 ... dn

输出格式

总收益
作业序列(编号从0开始)

输入样例

6
90 80 50 30 20 10
1 2 1 3 4 3

输出样例

220

[0, 1, 3, 4]

微笑分析:既然每个作业占时都一样,肯定先对收益排个序(此题的数据已帮你排好),能做就做,有冲突放弃。标准的贪心,局部最优来达到全局最优。

维护一个list。list[i]=j表示在当前遍历过程中,编号为 j 的作业的期限是第 i 大的。注意在遍历过程中,list中的内容可能会不断变化,即同一下标的元素也会不断变化。

微笑代码:


目录
相关文章
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
58 0
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
41 0
|
7月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-476 计算质数和
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-476 计算质数和
54 0
|
7月前
|
算法
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-贪心算法
62 0
|
7月前
|
算法 Java Serverless
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-444 算法训练 求和问题
60 1
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询
41 0
|
7月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
57 0
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-645 加法分解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-645 加法分解
41 0
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
65 1
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-633 加法分解
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-633 加法分解
45 0