简答题 偏难
#17999

运送物资 时间限制:2.0 s 内存限制:512.0 MB 题面描述 小杨管理着 m 辆货车,每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有…

运送物资

时间限制:2.0 s

内存限制:512.0 MB

题面描述

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

每次运送物资时,货车从初始运输站点出发,前往 A 市或 B 市,之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点,其中 A 市的坐标为 ,B 市的坐标为 x ,运输站点的坐标为 p 且有 0<p<x,货车每次去 A 市运送物资的总行驶路程为 2p,去 B 市运送物资的总行驶路程为 2(x−p)。

对于第 i 个运输站点,其位置为 pi 且至多作为 ci 辆车的初始运输站点。小杨想知道,在最优分配每辆货车的初始运输站点的情况下,所有货车每天的最短总行驶路程是多少。

输入格式

第一行包含三个正整数 n,m,x,代表运输站点数量,货车数量和两市距离。

之后 n 行,每行包含两个正整数 pi,ci,代表第 i 个运输站点的位置和最多容纳车辆数。

之后 m 行,每行包含两个正整数 ai,bi,代表第 i 辆货车每天需要向 A 市运送 ai 次物资,向 B 市运送 bi 次物资。

输出格式

输出一个正整数,代表所有货车每天的最短总行驶路程。


输入样例

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

输出样例

40186

样例解释

第1辆车的初始运输站点为站点 3,第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1,第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短,为 40186。

对于全部数据,保证有1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证 ∑ci≥m。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n, m, x = map(int, input().split()) st = [] for _ in range(n): p, c = map(int, input().split()) st.append((p, c)) st.sort() a = [0] * m b = [0] * m for i in range(m): a[i], b[i] = map(int, input().split()) neg = [] pos = [] res = 0 for i in range(m): if a[i] &gt;= b[i]: pos.append((a[i] - b[i], i)) else: neg.append((a[i] - b[i], i)) res += b[i] * x neg.sort() pos.sort(reverse=True) l, r = 0, n - 1 for i in neg: while r &gt;= 0 and st[r][1] == 0: r -= 1 res += (a[i[1]] - b[i[1]]) * st[r][0] st[r] = (st[r][0], st[r][1] - 1) for i in pos: while l &lt; n and st[l][1] == 0: l += 1 res += (a[i[1]] - b[i[1]]) * st[l][0] st[l] = (st[l][0], st[l][1] - 1) print(res * 2)</pre>
这道题暂未补解析。