信息学奥赛一本通 ybt 1608:【 例 3】任务安排 3 | 洛谷 P5785 [SDOI2012] 任务安排

【题目链接】

ybt 1608:【 例 3】任务安排 3
洛谷 P5785 [SDOI2012] 任务安排

【题目考点】

1. 动态规划:斜率优化动规
2. 单调队列
3. 二分答案

【解题思路】

与本题题面相同但问题规模不同的题目:
信息学奥赛一本通 1607:【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2
本题相比上题只有 t i t_i ti的数值范围从 t i ≤ 2 8 t_i\le 2^8 ti28,变为 ∣ t i ∣ ≤ 2 8 |t_i| \le 2^8 ti28,也就是 − 2 8 ≤ t i ≤ 2 8 -2^8 \le t_i \le 2^8 28ti28
斜率优化相关内容已在上题中有详细解释,本题不再赘述。请先看上题题解,而后再看本题题解。

本题中 t i t_i ti可能是负数,求出的前缀和 T i T_i Ti也可能是负数。
随着 i i i的增大 T i T_i Ti不再是单调递增的,直线斜率 K = T i + s K=T_i+s K=Ti+s随着 i i i的增大也不再是单调递增的。因此上题题解中8. 决策点队头出队中所述的方法不再适用。本题需要维护所有下凸壳上的决策点。

已知决策点比较条件为:
C j 1 < C j 2 C_{j_1}<C_{j_2} Cj1<Cj2的前提下:

  • 如果 k ( j 1 , j 2 ) > K k(j_1,j_2) > K k(j1,j2)>K,那么决策点 j 1 j_1 j1优于 j 2 j_2 j2
  • 如果 k ( j 1 , j 2 ) < K k(j_1,j_2) < K k(j1,j2)<K,那么决策点 j 2 j_2 j2优于 j 1 j_1 j1

决策点集的下凸壳上的所有决策点按 C j C_j Cj从小到大记为 q l , q l + 1 , . . . , q r q_l,q_{l+1},...,q_r ql,ql+1,...,qr,保存在一个单调队列中,相邻点连线的斜率是单调递增的:
k ( q l , q l + 1 ) < k ( q l + 1 , q l + 2 ) < . . . < k ( q r − 1 , q r ) k(q_l,q_{l+1})<k(q_{l+1},q_{l+2})<...<k(q_{r−1},q_r) k(ql,ql+1)<k(ql+1,ql+2)<...<k(qr1,qr)

那么从 q l q_l ql看到 q r q_r qr,找到第一个满足 k ( q m , q m + 1 ) ≥ K k(q_m,q_{m+1})≥K k(qm,qm+1)K的决策点 q m q_m qm q m q_m qm就是最优决策点。
如果没有满足条件的点,则选择队列最后一个点 q r q_r qr为最优决策点。
该过程可以通过二分答案完成

  • 答案变量: q q q数组下标m,初始范围 [ l , r ] [l, r] [l,r]
  • 最值:求最小值
  • 满足条件: k ( q m , q m + 1 ) ≥ K k(q_m,q_{m+1})≥K k(qm,qm+1)K

如果存在满足条件的决策点,返回二分答案的结果m,取最优决策点 q m q_m qm
如果不存在满足条件的决策点,二分答案的结果就是初始范围的右端点r,此时返回r,取到的最优决策点是 q r q_r qr

条件 k ( q m , q m + 1 ) ≥ K k(q_m,q_{m+1})≥K k(qm,qm+1)K经过十字相乘后变为 ( d p q m + 1 − d p q m ) ≥ K ( C q m + 1 − C q m ) (dp_{q_{m+1}}-dp_{q_m})\ge K (C_{q_{m+1}}-C_{q_m}) (dpqm+1dpqm)K(Cqm+1Cqm)
算法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

在这里插入图片描述
图示:
一种可能的情况:
i为1时,直线斜率为 K 1 K_1 K1,第一个满足条件的是 k ( q 3 , q 4 ) ≥ K 1 k(q_3,q_4)\ge K_1 k(q3,q4)K1,最优决策点为 q 3 q_3 q3
i为2时,直线斜率为 K 2 K_2 K2,第一个满足条件的是 k ( q 2 , q 3 ) ≥ K 2 k(q_2,q_3)\ge K_2 k(q2,q3)K2,最优决策点为 q 2 q_2 q2
i为3时,直线斜率为 K 3 K_3 K3,没有满足条件的点,最优决策点为最后一个点 q 5 q_5 q5

【题解代码】

解法1:斜率优化动规,二分查找最优决策点 O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define N 300005
long long n, s, t[N], c[N], T[N], C[N], dp[N];//dp[i]:前i个任务的所有子段划分方案中,执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用
int q[N];
int binarySearch(int l, int r, int k)//通过二分查找找到第一个满足k(q[m], q[m+1])>=k的m,返回m。找不到满足条件的点,会返回r。 
{while(l < r){int m = (l+r)/2;if((dp[q[m+1]]-dp[q[m]]) >= k*(C[q[m+1]]-C[q[m]]))r = m;elsel = m+1; } return l; 
}
int main()
{int l = 1, r = 0;//单调队列队头队尾下标 cin >> n >> s;for(int i = 1; i <= n; ++i){cin >> t[i] >> c[i];T[i] = T[i-1]+t[i];C[i] = C[i-1]+c[i];}q[++r] = 0;//加入(C[0],dp[0])点 for(int i = 1; i <= n; ++i){int b = binarySearch(l, r, T[i]+s);dp[i] = dp[q[b]]-(T[i]+s)*C[q[b]]+T[i]*C[i]+s*C[n];while(l < r && (dp[i]-dp[q[r]])*(C[q[r]]-C[q[r-1]]) <= (C[i]-C[q[r]])*(dp[q[r]]-dp[q[r-1]]))--r;q[++r] = i;}cout << dp[n];return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/11055.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LabVIEW无线齿轮监测系统

本案例介绍了基于LabVIEW的无线齿轮监测系统设计。该系统利用LabVIEW编程语言和改进的天牛须算法优化支持向量机&#xff0c;实现了无线齿轮故障监测。通过LabVIEW软件和相关硬件&#xff0c;可以实现对齿轮箱振动信号的采集、传输和故障识别&#xff0c;集远程采集、数据库存储…

Doki Doki Mods Maker小指南

-*- 做都做了&#xff0c;那就做到底吧。 -*- 前言&#xff1a; 项目的话&#xff0c;在莫盘里&#xff0c;在贴吧原帖下我有发具体地址。 这里是Doki Doki Mods Maker&#xff0c;是用来做DDLC Mods的小工具。 说是“Mods”&#xff0c;实则不然&#xff0c;这个是我从零仿…

Node.js——body-parser、防盗链、路由模块化、express-generator应用生成器

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…

三、js笔记

(一)JavaScript概述 1、发展历史 ScriptEase.(客户端执行的语言):1992年Nombas开发出C-minus-minus(C--)的嵌入式脚本语言(最初绑定在CEnvi软件中).后将其改名ScriptEase.(客户端执行的语言)Javascript:Netscape(网景)接收Nombas的理念,(Brendan Eich)在其Netscape Navigat…

JavaScript作用域详解

前言 作用域是JavaScript中一个重要的概念&#xff0c;它决定了变量和函数在代码中的可访问性和可见性。了解JavaScript的作用域对于编写高效、可维护的代码至关重要。本文将深入介绍JavaScript作用域相关的知识点&#xff0c;其中包括作用域类型&#xff0c;作用域链&#xff…

如何使用SliverList组件

文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了沉浸式状态栏相关的内容&#xff0c;本章回中将介绍SliverList组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的SliverList组件是一种列表类组件&#xff0c;类似我们之前介…

vsnprintf() 将可变参数格式化输出到字符数组

vsnprintf{} 将可变参数格式化输出到一个字符数组 1. function vsnprintf()1.1. const int num_bytes vsnprintf(NULL, 0, format, arg); 2. Parameters3. Return value4. Example5. llama.cppReferences 1. function vsnprintf() https://cplusplus.com/reference/cstdio/vs…

一文大白话讲清楚webpack基本使用——17——Tree Shaking

文章目录 一文大白话讲清楚webpack基本使用——17——Tree Shaking1. 建议按文章顺序从头看&#xff0c;一看到底&#xff0c;豁然开朗2. 啥叫Tree Shaking3. 什么是死代码&#xff0c;怎么来的3. Tree Shaking的流程3.1 标记3.2 利用Terser摇起来 4. 具体使用方式4.1 适用前提…

仿真设计|基于51单片机的温湿度、一氧化碳、甲醛检测报警系统

目录 具体实现功能 设计介绍 51单片机简介 资料内容 仿真实现&#xff08;protues8.7&#xff09; 程序&#xff08;Keil5&#xff09; 全部内容 资料获取 具体实现功能 &#xff08;1&#xff09;温湿度传感器、CO传感器、甲醛传感器实时检测温湿度值、CO值和甲醛值进…

几种K8s运维管理平台对比说明

目录 深入体验**结论**对比分析表格**1. 功能对比****2. 用户界面****3. 多租户支持****4. DevOps支持** 细对比分析1. **Kuboard**2. **xkube**3. **KubeSphere**4. **Dashboard****对比总结** 深入体验 KuboardxkubeKubeSphereDashboard 结论 如果您需要一个功能全面且适合…

GenAI 在金融服务领域的应用:2025 年的重点是什么

作者&#xff1a;来自 Elastic Karen Mcdermott GenAI 不是魔法 我最近参加了 ElasticON&#xff0c;我们与纽约 Elastic 社区一起度过了一天&#xff0c;讨论了使用检索增强生成 (retrieval augmented generation - RAG) 为大型语言模型 (large language models - LLMs) 提供…

如何对系统调用进行扩展?

扩展系统调用是操作系统开发中的一个重要任务。系统调用是用户程序与操作系统内核之间的接口,允许用户程序执行内核级操作(如文件操作、进程管理、内存管理等)。扩展系统调用通常包括以下几个步骤: 一、定义新系统调用 扩展系统调用首先需要定义新的系统调用的功能。系统…

LightM-UNet(2024 CVPR)

论文标题LightM-UNet: Mamba Assists in Lightweight UNet for Medical Image Segmentation论文作者Weibin Liao, Yinghao Zhu, Xinyuan Wang, Chengwei Pan, Yasha Wang and Liantao Ma发表日期2024年01月01日GB引用> Weibin Liao, Yinghao Zhu, Xinyuan Wang, et al. Ligh…

Cubemx文件系统挂载多设备

cubumx版本&#xff1a;6.13.0 芯片&#xff1a;STM32F407VET6 在上一篇文章中介绍了Cubemx的FATFS和SD卡的配置&#xff0c;由于SD卡使用的是SDIO通讯&#xff0c;因此具体驱动不需要自己实现&#xff0c;Cubemx中就可以直接配置然后生成SDIO的驱动&#xff0c;并将SD卡驱动和…

电子电气架构 --- 汽车电子拓扑架构的演进过程

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…

2025 年,链上固定收益领域迈向新时代

“基于期限的债券市场崛起与Secured Finance的坚定承诺” 2025年&#xff0c;传统资产——尤其是股票和债券——大规模涌入区块链的浪潮将创造历史。BlackRock 首席执行官 Larry Fink 近期在彭博直播中表示&#xff0c;代币化股票和债券将逐步融入链上生态&#xff0c;将进一步…

数据密码解锁之DeepSeek 和其他 AI 大模型对比的神秘面纱

本篇将揭露DeepSeek 和其他 AI 大模型差异所在。 目录 ​编辑 一本篇背景&#xff1a; 二性能对比&#xff1a; 2.1训练效率&#xff1a; 2.2推理速度&#xff1a; 三语言理解与生成能力对比&#xff1a; 3.1语言理解&#xff1a; 3.2语言生成&#xff1a; 四本篇小结…

Ollama部署指南

什么是Ollama&#xff1f; Ollama是一个专为在本地机器上便捷部署和运行大型语言模型&#xff08;LLM&#xff09;而设计的开源工具。 如何部署Ollama&#xff1f; 我是使用的云平台&#xff0c;大家也可以根据自己的云平台的特点进行适当的调整。 使用系统&#xff1a;ubun…

群晖Alist套件无法挂载到群晖webdav,报错【连接被服务器拒绝】

声明&#xff1a;我不是用docker安装的 在套件中心安装矿神的Alist套件后&#xff0c;想把夸克挂载到群晖上&#xff0c;方便复制文件的&#xff0c;哪知道一直报错&#xff0c;最后发现问题出在两个地方&#xff1a; 1&#xff09;挂载的路径中&#xff0c;直接填 dav &…

Kubernetes组成及常用命令

Pods(k8s最小操作单元)ReplicaSet & Label(k8s副本集和标签)Deployments(声明式配置)Services(服务)k8s常用命令Kubernetes(简称K8s)是一个开源的容器编排系统,用于自动化应用程序的部署、扩展和管理。自2014年发布以来,K8s迅速成为容器编排领域的行业标准,被…