简答题 偏难
#20673

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

运送物资

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨管理着 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 个运输站点,其位置为 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:cpp;toolbar:false;">#include&lt;bits/stdc++.h&gt; using namespace std; #define ll long long const int N = 1e5+10; int n,m; ll x; vector&lt;pair&lt;int,int&gt; &gt; st; int a[N],b[N]; int main(){ cin&gt;&gt;n&gt;&gt;m&gt;&gt;x; for(int i=1;i&lt;=n;i++){ int p,c; cin&gt;&gt;p&gt;&gt;c; st.push_back(make_pair(p,c)); } sort(st.begin(),st.end()); for(int i=1;i&lt;=m;i++){ cin&gt;&gt;a[i]&gt;&gt;b[i]; } vector&lt;pair&lt;int,int&gt; &gt; neg,pos; ll res=0; for(int i=1;i&lt;=m;i++){ if(a[i]&gt;=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&gt;=1&amp;&amp;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&lt;=n&amp;&amp;st[l].second==0)l++; res+=1ll*(a[i.second]-b[i.second])*st[l].first; st[l].second-=1; } cout&lt;&lt;res*2&lt;&lt;"\n"; }</pre>
这道题暂未补解析。