A29840. 运送物资
填空题
困难
知识点
题目描述
运送物资
时间限制：2.0 s 内存限制：512.0 MB
题目描述
小杨管理着 m 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 ，B 市的坐标为 ，运输站点的坐标为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
样例解释
第 辆车的初始运输站点为站点3，第2辆车的初始运输站点为站点 。第3辆车的初始运输站点为站点1，第4辆车的初始运输站点为站点3。此时总行驶路程最短，40186。
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
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";
}
上一题
下一题