【贪心交换排序】题解：P11376 [GESP202412 六级] 运送物资_贪心模型_排序_模拟

文章目录题目描述题解时间限制1.00s内存限制512.00MB提供者沉石鱼惊旋难度普及/提高−标签贪心排序GESP2024题目描述小杨管理着m mm辆货车每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有n nn个运输站点这些站点位于 A 市和 B 市之间。每次运送物资时货车从初始运输站点出发前往 A 市或 B 市之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点其中 A 市的坐标为0 00B 市的坐标为x xx运输站点的坐标为p pp且有0 p x 0 \lt p \lt x0px。货车每次去 A 市运送物资的总行驶路程为2 p 2p2p去 B 市运送物资的总行驶路程为2 ( x − p ) 2(x - p)2(x−p)。对于第i ii个运输站点其位置为p i p_ipi且至多作为c i c_ici辆车的初始运输站点。小杨想知道在最优分配每辆货车的初始运输站点的情况下所有货车每天的最短总行驶路程是多少。输入格式第一行包含三个正整数n , m , x n,m,xn,m,x代表运输站点数量、货车数量和两市距离。之后n nn行每行包含两个正整数p i p_ipi和c i c_ici代表第i ii个运输站点的位置和最多容纳车辆数。之后m mm行每行包含两个正整数a i a_iai和b i b_ibi代表第i ii辆货车每天需要向 A 市运送a i a_iai次物资向 B 市运送b i b_ibi次物资。输出格式输出一个正整数代表所有货车每天的最短总行驶路程。输入输出样例 #1输入 #13 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000输出 #140186说明/提示第1 11辆车的初始运输站点为站点3 33第2 22辆车的初始运输站点为站点2 22。第3 33辆车的初始运输站点为站点1 11第4 44辆车的初始运输站点为站点3 33。此时总驶路程最短为40186 4018640186。子任务编号数据点占比n nns ssc i c_ici1 1120 % 20\%20%2 222 221 112 2220 % 20\%20%≤ 10 5 \leq 10^5≤105≤ 10 5 \leq 10^5≤1051 113 3360 % 60\%60%≤ 10 5 \leq 10^5≤105≤ 10 5 \leq 10^5≤105≤ 10 5 \leq 10^5≤105对于全部数据保证有1 ≤ n , m ≤ 10 5 1\leq n,m\leq 10^51≤n,m≤1052 ≤ x ≤ 10 8 2\leq x\leq 10^82≤x≤1080 p i x 0\lt p_i\lt x0pix1 ≤ c i ≤ 10 5 1\leq c_i\leq 10^51≤ci≤1050 ≤ a i , b i ≤ 10 5 0\leq a_i,b_i\leq 10^50≤ai,bi≤105。数据保证∑ c i ≥ m \sum c_i\geq m∑ci≥m。题解/* 首先考虑列出每辆车的总行驶路程s2*a[i]*p2*b[i]*(x-p) 根据直觉a[i]b[i]的车应当优先分配靠左的p[x]a[i]b[i]的车应该优先分配靠右的p[x]所以需要排序解决那怎么排序呢在所有a[i]b[i]的车中贪心地想a[i]越多的应该越靠左但同时也要考虑b[i]的影响所以应该是a[i]-b[i]越大的越靠左安排 a[i]b[i]同理证明排序不等式适用于代价两两不相关的交换/排序问题假设对于两辆车i,ji在p1j在p2如果把i移到j更优就要求原来的总代价大于交换后的总代价即 2*a[i]*p12*b[i]*(x-p1) 2*a[j]*p22*b[j]*(x-p2) 2*a[i]*p22*b[i]*(x-p2) 2*a[j]*p12*b[j]*(x-p1) a[i]*p1 - b[i]*p1 a[j]*p2 - b[j]*p2 a[i]*p2 - b[i]*p2 a[j]*p1 - b[j]*p1 a[i]*(p1-p2) b[i]*(p2-p1) a[j]*(p1-p2) b[j]*(p2-p1) (a[i]-b[i])(p1-p2) (a[j]-b[j])(p1-p2) a[i]-b[i] a[j]-b[j] 然后贪心模拟即可注意a[i]b[i]的情况可以与a[i]b[i]的情况一同处理变成a[i]b[i] */#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1e55;intn,m,x,cnt1,cnt2;structInfo{intp,c;}t[N];// 运输站点structNode{inta,b;}f[N],g[N];// 货车 f:a[i]b[i] g:a[i]b[i]voidsolve(){cinnmx;for(inti1;in;i){cint[i].pt[i].c;}for(inti1;im;i){intaa,bb;cinaabb;if(aabb)f[cnt1]{aa,bb};elseg[cnt2]{aa,bb};}sort(t1,tn1,[](Info p1,Info p2){returnp1.pp2.p;});sort(f1,fcnt11,[](Node p1,Node p2){returnp1.a-p1.bp2.a-p2.b;});sort(g1,gcnt21,[](Node p1,Node p2){returnp1.b-p1.ap2.b-p2.a;});intnow1;ll ans0;for(inti1;icnt1;i){if(t[now].c0)now;ans2LL*f[i].a*t[now].p2LL*f[i].b*(x-t[now].p);t[now].c--;}nown;for(inti1;icnt2;i){if(t[now].c0)now--;ans2LL*g[i].a*t[now].p2LL*g[i].b*(x-t[now].p);t[now].c--;}coutans\n;}signedmain(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);solve();return0;}

【贪心交换排序】题解：P11376 [GESP202412 六级] 运送物资_贪心模型_排序_模拟_C++算法竞赛

相关推荐

【CPU】Hypervisor 中 LHP / LWP 问题

开拓者：正义之怒职业构建：3步走完开卡到毕业

[Web3] 去中心化基石 - BIP铁三角(BIP32/39/44)

更多资讯

C# GDI+自绘工控仪表控件：圆表直表旋钮开关指示灯

Windows 上开发 Expo iOS，用 KXBuild 本地生成工程、真机调试与打包 ipa

UDP组播实现IPC自动探测：Python收包解析与批量巡检避坑

7代酷睿Win7核显驱动手动改INF安装指南

C# WinForms 自绘仪表控件：圆表、直表、旋钮、开关与指示灯实战

第九篇：《分区表实战：范围分区、列表分区、哈希分区》

今日更新

学生选课系统DFD图绘制指南：边界划分与分层校验实战

JIRA敏捷落地：Scrum角色权限、Sprint与燃尽图避坑指南

SEMI S8人机工程验收实战：从条款拆解到现场实测的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？