1 solutions
-
1
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=1e5+10; int n,m,x; vector<PII> 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({p,c}); //站点位置和车辆数目 } sort(st.begin(),st.end()); //按照位置排序 for(int i=1;i<=m;i++) //左边和右边的数量 { cin>>a[i]>>b[i]; } vector<PII> right,left; LL res=0; for(int i=1;i<=m;i++)//枚举货车 { if(a[i]>=b[i]) //优先去前面(p) { left.push_back({a[i]-b[i],i}); } else //优先去后面(x-p) { right.push_back({a[i]-b[i],i}); } res+=1LL*b[i]*x; //计算 } sort(right.begin(),right.end()); //从小到大排序 sort(left.begin(),left.end()); //从小到大排序 reverse(left.begin(),left.end()); //从大到小排序 int l=0,r=n-1; //站点的起点和终点 for(auto i:right) //后面 { while(r>=1&&st[r].second==0) r--; //找到后面第一个非0的位置 res+=1ll*(a[i.second]-b[i.second])*st[r].first; //减去到前面的距离 st[r].second-=1; //这个站点少了一辆车子 } for(auto i:left) //前面 { while(l<=n&&st[l].second==0) l++; //找到前面的第一个非0的位置 res+=1ll*(a[i.second]-b[i.second])*st[l].first; //累加前面的距离 st[l].second-=1; } cout<<res*2; //来回距离 return 0; }
Information
- ID
- 2220
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 2
- Accepted
- 2
- Uploaded By