4665: 【GESP2412六级】运送物资
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
$m$ 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有$n$ 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为$0$ ，B 市的坐标为$x$ ，运输站点的坐标为$p$ 且有$0< p < x$ ，货车每次去 A 市运送物资的总行驶路程为 $2p$，去 B 市运送物资的总行驶路程为$2(x-p)$ 。
对于第$i$ 个运输站点，其位置为$p_i$ 且至多作为$c_i$ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为$0$ ，B 市的坐标为$x$ ，运输站点的坐标为$p$ 且有$0< p < x$ ，货车每次去 A 市运送物资的总行驶路程为 $2p$，去 B 市运送物资的总行驶路程为$2(x-p)$ 。
对于第$i$ 个运输站点，其位置为$p_i$ 且至多作为$c_i$ 辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
输入
第一行包含三个正整数$n,m,x$ ，代表运输站点数量，货车数量和两市距离。
之后$n$ 行，每行包含两个正整数$p_i,c_i$ ，代表第$i$ 个运输站点的位置和最多容纳车辆数。
之后$m$ 行，每行包含两个正整数$a_i,b_i$ ，代表第$i$ 辆货车每天需要向 A 市运送$a_i$ 次物资，向 B 市运送$b_i$ 次物资。
之后$n$ 行，每行包含两个正整数$p_i,c_i$ ，代表第$i$ 个运输站点的位置和最多容纳车辆数。
之后$m$ 行，每行包含两个正整数$a_i,b_i$ ，代表第$i$ 辆货车每天需要向 A 市运送$a_i$ 次物资，向 B 市运送$b_i$ 次物资。
输出
输出一个正整数，代表所有货车每天的最短总行驶路程。
样例输入 复制
3 4 10
1 1
2 1
8 3
5 3
7 2
9 0
1 10000样例输出 复制
40186提示
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int n, m;
ll x;
vector < pair < int, int > > st;
int a[N], b[N];
int main() {
cin >> n >> m >> x;
for (int i = 1; i <= n; i++) {
int p, c;
cin >> p >> c;
st.push_back(make_pair(p, c));
}
sort(st.begin(), st.end());
for (int i = 1; i <= m; i++) {
cin >> a[i] >> b[i];
}
vector < pair < int, int > > neg, pos;
ll res = 0;
for (int i = 1; i <= m; i++) {
if (a[i] >= b[i])
pos.push_back(make_pair(a[i] - b[i], i));
else {
neg.push_back(make_pair(a[i] - b[i], i));
}
res += 1ll * b[i] * x;
}
sort(neg.begin(), neg.end());
sort(pos.begin(), pos.end());
reverse(pos.begin(), pos.end());
int l = 0, r = n - 1;
for (auto i: neg) {
while (r >= 1 && st[r].second == 0) r--;
res += 1ll * (a[i.second] - b[i.second]) * st[r].first;
st[r].second -= 1;
}
for (auto i: pos) {
while (l <= n && st[l].second == 0) l++;
res += 1ll * (a[i.second] - b[i.second]) * st[l].first;
st[l].second -= 1;
}
cout << res * 2 << "\n";
}