当前位置: 首页 > news >正文

做网站客户尾款老不给怎么办芜湖做网站的公司

做网站客户尾款老不给怎么办,芜湖做网站的公司,上传下载网站建设,上海静安网站制作题目链接 Leetcode.1665 完成所有任务的最少初始能量 Rating : 1901 题目描述 给你一个任务数组 tasks,其中 tasks[i] [actuali, minimumi]: actuali是完成第 i 个任务 需要耗费 的实际能量。minimumi是开始第 i 个任务前需要达到的最低能…

题目链接

Leetcode.1665 完成所有任务的最少初始能量 Rating : 1901

题目描述

给你一个任务数组 tasks,其中 tasks[i] = [actuali, minimumi]

  • actuali是完成第 i 个任务 需要耗费 的实际能量。
  • minimumi是开始第 i 个任务前需要达到的最低能量

比方说,如果任务为 ````[10, 12]```且你当前的能量为 11 ,那么你不能开始这个任务。如果你当前的能量为 13 ,你可以完成这个任务,且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1:

输入:tasks = [[1,2],[2,4],[4,8]]
输出:8
解释:
一开始有 8 能量,我们按照如下顺序完成任务:
- 完成第 3 个任务,剩余能量为 8 - 4 = 4 。
- 完成第 2 个任务,剩余能量为 4 - 2 = 2 。
- 完成第 1 个任务,剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余,但是如果一开始只有 7 能量是不能完成所有任务的,因为我们无法开始第 3 个任务。

示例 2:

输入:tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出:32
解释:
一开始有 32 能量,我们按照如下顺序完成任务:
- 完成第 1 个任务,剩余能量为 32 - 1 = 31 。
- 完成第 2 个任务,剩余能量为 31 - 2 = 29 。
- 完成第 3 个任务,剩余能量为 29 - 10 = 19 。
- 完成第 4 个任务,剩余能量为 19 - 10 = 9 。
- 完成第 5 个任务,剩余能量为 9 - 8 = 1 。

示例 3:

输入:tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出:27
解释:
一开始有 27 能量,我们按照如下顺序完成任务:
- 完成第 5 个任务,剩余能量为 27 - 5 = 22 。
- 完成第 2 个任务,剩余能量为 22 - 2 = 20 。
- 完成第 3 个任务,剩余能量为 20 - 3 = 17 。
- 完成第 1 个任务,剩余能量为 17 - 1 = 16 。
- 完成第 4 个任务,剩余能量为 16 - 4 = 12 。
- 完成第 6 个任务,剩余能量为 12 - 6 = 6 。

提示:

  • 1<=tasks.length<=1051 <= tasks.length <= 10^51<=tasks.length<=105
  • 1<=actual​i<=minimumi<=1041 <= actual​i <= minimumi <= 10^41<=actuali<=minimumi<=104

解法:贪心 + 排序

我们假设 ppp 为能够完成所有任务的能量。有 (a0,m0),(a1,m1),(a2,m2),(a3,m3),....,(an−1,mn−1)(a_0,m_0),(a_1,m_1) ,(a_2,m_2),(a_3,m_3),....,(a_{n-1},m_{n-1})(a0,m0),(a1,m1),(a2,m2),(a3,m3),....,(an1,mn1),共 nnn 个任务。

按照题目的要求,如下不等式成立:

  • p≥m0p \geq m_0pm0
  • p−a0≥m1p - a_0 \geq m_1pa0m1
  • p−a0−a1≥m2p - a_0 - a_1 \geq m_2pa0a1m2
  • p−a0−a1−a2≥m3p - a_0 - a_1 - a_2 \geq m_3pa0a1a2m3
  • p−a0−a1−a2−a3−...−an−2≥mn−1p - a_0 - a_1 - a_2 - a_3 - ...-a_{n-2} \geq m_{n-1}pa0a1a2a3...an2mn1

将其整理一下,得:

  • p≥m0p \geq m_0pm0
  • p≥a0+m1p \geq a_0 + m_1pa0+m1
  • p≥a0+a1+m2p \geq a_0 +a_1 + m_2pa0+a1+m2
  • p≥a0+a1+a2+m3p \geq a_0 +a_1 + a_2 + m_3pa0+a1+a2+m3
  • p≥a0+a1+a2+a3+....+an−2+mn−1p \geq a_0 +a_1 + a_2 + a_3 + .... +a_{n-2} + m_{n-1}pa0+a1+a2+a3+....+an2+mn1

由于我们要求的是最少的能量,即我们要使 ppp 的最大值 最小化

我们现在考虑,是否能让上面 n 个不等式右侧的最大值 变小

我们可以尝试交换相连的两项,看看会发生什么。交换 (ai,mi)(a_i,m_i)(ai,mi)(ai+1,mi+1)(a_{i+1},m_{i+1})(ai+1,mi+1)两项。

交换之前:

  • p≥a0+a1+a2+a3+....+ai−1+mi=P(i)p \geq a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + m_i = P(i)pa0+a1+a2+a3+....+ai1+mi=P(i)
  • p≥a0+a1+a2+a3+....+ai−1+ai+mi+1=P(i+1)p \geq a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + a_i + m_{i+1} = P(i+1)pa0+a1+a2+a3+....+ai1+ai+mi+1=P(i+1)

交换之后:

  • p≥a0+a1+a2+a3+....+ai−1+mi+1=P′(i)p \geq a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + m_{i+1} = P'(i)pa0+a1+a2+a3+....+ai1+mi+1=P(i)
  • p≥a0+a1+a2+a3+....+ai−1+ai+1+mi=P′(i+1)p \geq a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + a_{i+1} + m_i = P'(i+1)pa0+a1+a2+a3+....+ai1+ai+1+mi=P(i+1)

暂时只考虑这两项。交换之前的最大值为:max{P(i),P(i+1)}max\{P(i) , P(i+1)\}max{P(i),P(i+1)};交换之后的最大值为: max{P′(i),P′(i+1)}max\{P'(i) , P'(i+1)\}max{P(i),P(i+1)}

因为 P′(i+1)>P(i)P'(i+1) > P(i)P(i+1)>P(i) , P(i+1)>P′(i)P(i+1) > P'(i)P(i+1)>P(i)

我们要想让交换之后的最大值变小,即 max{P′(i),P′(i+1)}<max{P(i),P(i+1)}max\{P'(i) , P'(i+1)\} < max\{P(i) , P(i+1)\}max{P(i),P(i+1)}<max{P(i),P(i+1)}

等价于 P′(i+1)<P(i+1)P'(i+1) < P(i+1)P(i+1)<P(i+1),即 a0+a1+a2+a3+....+ai−1+ai+1+mi<a0+a1+a2+a3+....+ai−1+ai+mi+1a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + a_{i+1} + m_i < a_0 +a_1 + a_2 + a_3 + .... +a_{i-1} + a_i + m_{i+1}a0+a1+a2+a3+....+ai1+ai+1+mi<a0+a1+a2+a3+....+ai1+ai+mi+1

化简得,ai−mi>ai+1−mi+1a_i - m_i > a_{i+1} - m_{i+1}aimi>ai+1mi+1

所以我们要做的就是,找出所有的满足这样条件 ai−mi>ai+1−mi+1a_i - m_i > a_{i+1} - m_{i+1}aimi>ai+1mi+1 的相连两项,并将它们交换位置。这样做不一定会让最大值减小,但是绝对不会让最大值增大。

实际上我们没必要去模拟这个过程。我们只需要让 tasks 按照 ai−mia_i - m_iaimi从小到大的排序,最后再遍历模拟这个求最大值的过程即可。

时间复杂度:O(nlogn)O(nlogn)O(nlogn)

C++代码:

class Solution {
public:int minimumEffort(vector<vector<int>>& tasks) {sort(tasks.begin(),tasks.end(),[&](auto &a,auto &b){return a[0] - a[1] < b[0] - b[1];}) ;int p = 0 , s = 0;for(auto &e:tasks){p = max(p,s + e[1]);s += e[0];}return p;}
};
http://www.yayakq.cn/news/932355/

相关文章:

  • 网站歌曲代码网站源码在哪看
  • 网站职业技能培训学校设计师必逛网站排名
  • 壁画网站建设福州市网站建设公司
  • 哪个网站可以找做软件兼职的谷歌 网站做推广
  • 营销型网站设计价格大学生毕业设计课题做网站
  • 临沂做百度网站软件公司怎样做网站表白墙
  • 手机网站建设图片2016网站设计趋势
  • 黄岛区做网站的如何制作简单的网站
  • 六安电商网站建设哪家好手表价格网站
  • 北京自助建站系统房产中介网站开发与设计代码
  • 网站建设问卷调查九江建筑工程有限公司
  • 环保设备网站怎么做虾皮购物网站怎么做
  • 网站升级改造建设方案wordpress快速清除本地图片
  • 银行网站维护是做哪些设计方案构思和设计过程
  • 辽阳网站网站建设如何制作视频教程
  • 如何加强网站信息管理建设wordpress网站go.php跳转
  • 关于制作网站收费标准众云网联做的网站效果好吗
  • 网站做外链好嘛wordpress媒体库下载
  • 网站底部广告wordpress主题汉化软件
  • 婴幼儿用品销售网站开发报告企业软件定制开发报价
  • 温州网站 公司东莞网站设计及拍摄方案公司
  • 自动采集网站php源码库尔勒网站商城建设
  • 制定一网站建设的市场定位的方案以图搜图百度识图
  • 江门网站建设技术托管网站恶意注册
  • 电影网站开发库表结构天辰建设信息网
  • 西安做网站公司哪个好网站建设流程教案
  • 淘宝网做宝贝详情用哪个网站wordpress模板影视
  • 手机 网站百度seo引流怎么做
  • 网站违反了 google 质量指南手机怎么制作自己的网站
  • 蘑菇街网站模板国内禁用的国外网站