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

文章目录题目描述题解时间限制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_ici​1 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 x0pi​x1 ≤ 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;}