新闻详情

新闻详情

首页 / 资讯中心 / 详情

贪心题目:两地调度

发布时间:2026/11/16 6:25:38来源:尧图网络
贪心题目:两地调度
文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题两地调度出处1029. 两地调度难度4 级题目描述要求公司计划面试2n \texttt{2n}2n人。给定一个数组costs \texttt{costs}costs其中costs[i] [aCost i , bCost i ] \texttt{costs[i] [aCost}_\texttt{i}\texttt{, bCost}_\texttt{i}\texttt{]}costs[i] [aCosti​, bCosti​]表示第i \texttt{i}i人飞往 A 市的费用为aCost i \texttt{aCost}_\texttt{i}aCosti​飞往 B 市的费用为bCost i \texttt{bCost}_\texttt{i}bCosti​。返回当每个城市都有n \texttt{n}n人抵达的情况下将每个人都飞到其中一座城市的最低费用。示例示例 1输入costs [[10,20],[30,200],[400,50],[30,20]] \texttt{costs [[10,20],[30,200],[400,50],[30,20]]}costs [[10,20],[30,200],[400,50],[30,20]]输出110 \texttt{110}110解释第一个人去 A 市费用为10 \texttt{10}10。第二个人去 A 市费用为30 \texttt{30}30。第三个人去 B 市费用为50 \texttt{50}50。第四个人去 B 市费用为20 \texttt{20}20。最低总费用为10 30 50 20 110 \texttt{10} \texttt{30} \texttt{50} \texttt{20} \texttt{110}10305020110每个城市都有一半的人在面试。示例 2输入costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] \texttt{costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]}costs [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]输出1859 \texttt{1859}1859示例 3输入costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] \texttt{costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]}costs [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]输出3086 \texttt{3086}3086数据范围2 × n costs.length \texttt{2} \times \texttt{n} \texttt{costs.length}2×ncosts.length2 ≤ costs.length ≤ 100 \texttt{2} \le \texttt{costs.length} \le \texttt{100}2≤costs.length≤100costs.length \texttt{costs.length}costs.length为偶数1 ≤ aCost i , bCost i ≤ 1000 \texttt{1} \le \texttt{aCost}_\texttt{i}\texttt{, bCost}_\texttt{i} \le \texttt{1000}1≤aCosti​, bCosti​≤1000解法思路和算法为了计算每个城市都有n nn人抵达的最低费用可以首先计算全部2 n 2n2n人都抵达 A 市的总费用total \textit{total}total然后选其中n nn人换到 B 市更新总费用并使总费用最低。对于0 ≤ i 2 n 0 \le i 2n0≤i2n将第i ii人从 A 市换到 B 市之后总费用total \textit{total}total变成total ( bCost i − aCost i ) \textit{total} (\textit{bCost}_i - \textit{aCost}_i)total(bCosti​−aCosti​)。以下将每个人抵达 B 市的费用与抵达 A 市的费用之差称为费用差即费用差为bCost − aCost \textit{bCost} - \textit{aCost}bCost−aCost费用差可能是正数、零或负数。为了使总费用最低应使抵达 B 市的n nn个人的费用差之和最小化因此应选费用差最小的n nn个人。该做法是贪心策略贪心策略的正确性说明如下。假设全部2 n 2n2n人都抵达 A 市的总费用是total \textit{total}total费用差最小的n nn个人的费用差之和是x xx则费用差最小的n nn个人抵达 B 市的情况下总费用是total x \textit{total} xtotalx。如果选一个费用差更大的人抵达 B 市则需要替换费用差最小的n nn个人之一替换之后抵达 B 市的n nn个人的费用差之和一定大于等于x xx总费用一定大于等于total x \textit{total} xtotalx不可能有更低的总费用。因此选费用差最小的n nn个人可以使总费用最低。具体做法如下。计算全部2 n 2n2n人都抵达 A 市的总费用total \textit{total}total。创建长度为2 n 2n2n的数组differences \textit{differences}differences记录每个人的费用差对于0 ≤ i 2 n 0 \le i 2n0≤i2n计算differences [ i ] costs [ i ] [ 1 ] − costs [ i ] [ 0 ] \textit{differences}[i] \textit{costs}[i][1] - \textit{costs}[i][0]differences[i]costs[i][1]−costs[i][0]。将数组differences \textit{differences}differences按升序排序。遍历数组differences \textit{differences}differences的前n nn个元素即最小的n nn个元素对于0 ≤ i n 0 \le i n0≤in将total \textit{total}total更新为total differences [ i ] \textit{total} \textit{differences}[i]totaldifferences[i]。遍历结束之后的total \textit{total}total即为每个城市都有n nn人抵达的最低费用。代码classSolution{publicinttwoCitySchedCost(int[][]costs){inttotal0;intlengthcosts.length;intnlength/2;int[]differencesnewint[length];for(inti0;ilength;i){totalcosts[i][0];differences[i]costs[i][1]-costs[i][0];}Arrays.sort(differences);for(inti0;in;i){totaldifferences[i];}returntotal;}}复杂度分析时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)其中n nn是数组costs \textit{costs}costs的长度的一半。数组costs \textit{costs}costs的长度是2 n 2n2n计算数组differences \textit{differences}differences需要O ( 2 n ) O ( n ) O(2n) O(n)O(2n)O(n)的时间将数组differences \textit{differences}differences排序需要O ( 2 n log ⁡ ( 2 n ) ) O ( n log ⁡ n ) O(2n \log (2n)) O(n \log n)O(2nlog(2n))O(nlogn)的时间排序之后遍历数组differences \textit{differences}differences的前n nn个元素需要O ( n ) O(n)O(n)的时间因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。空间复杂度O ( n ) O(n)O(n)其中n nn是数组costs \textit{costs}costs的长度的一半。创建数组differences \textit{differences}differences需要O ( 2 n ) O ( n ) O(2n) O(n)O(2n)O(n)的空间将数组differences \textit{differences}differences排序需要O ( log ⁡ ( 2 n ) ) O ( log ⁡ n ) O(\log (2n)) O(\log n)O(log(2n))O(logn)的递归调用栈空间因此空间复杂度是O ( n ) O(n)O(n)。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉