题目描述

小杨管理着m mm辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有n nn个运输站点，这些站点位于 A 市和 B 市之间。

每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为0 00，B 市的坐标为x xx，运输站点的坐标为p pp且有0 < p < x 0 \lt p \lt x0<p<x。货车每次去 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

输入 #1

3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000

输出 #1

40186

说明/提示

第1 11辆车的初始运输站点为站点3 33，第2 22辆车的初始运输站点为站点2 22。第3 33辆车的初始运输站点为站点1 11，第4 44辆车的初始运输站点为站点3 33。此时总驶路程最短，为40186 4018640186。

对于全部数据，保证有1 ≤ n , m ≤ 10 5 1\leq n,m\leq 10^51≤n,m≤105，2 ≤ x ≤ 10 8 2\leq x\leq 10^82≤x≤108，0 < p i < x 0\lt p_i\lt x0<pi​<x，1 ≤ c i ≤ 10 5 1\leq c_i\leq 10^51≤ci​≤105，0 ≤ 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。

题解

/* 首先考虑列出每辆车的总行驶路程：s=2*a[i]*p+2*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,j，i在p1，j在p2，如果把i移到j更优，就要求原来的总代价大于交换后的总代价，即： 2*a[i]*p1+2*b[i]*(x-p1) + 2*a[j]*p2+2*b[j]*(x-p2) > 2*a[i]*p2+2*b[i]*(x-p2) + 2*a[j]*p1+2*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] */#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+5;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(){cin>>n>>m>>x;for(inti=1;i<=n;i++){cin>>t[i].p>>t[i].c;}for(inti=1;i<=m;i++){intaa,bb;cin>>aa>>bb;if(aa>=bb)f[++cnt1]={aa,bb};elseg[++cnt2]={aa,bb};}sort(t+1,t+n+1,[](Info p1,Info p2){returnp1.p<p2.p;});sort(f+1,f+cnt1+1,[](Node p1,Node p2){returnp1.a-p1.b>p2.a-p2.b;});sort(g+1,g+cnt2+1,[](Node p1,Node p2){returnp1.b-p1.a>p2.b-p2.a;});intnow=1;ll ans=0;for(inti=1;i<=cnt1;i++){if(t[now].c==0)now++;ans+=2LL*f[i].a*t[now].p+2LL*f[i].b*(x-t[now].p);t[now].c--;}now=n;for(inti=1;i<=cnt2;i++){if(t[now].c==0)now--;ans+=2LL*g[i].a*t[now].p+2LL*g[i].b*(x-t[now].p);t[now].c--;}cout<<ans<<'\n';}signedmain(){ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);solve();return0;}