1 solutions
-
0
C++ :
#include<bits/stdc++.h> using namespace std; #define ll long long /*思路: 对于一辆货车c(距离A为a,距离B为b),选择坐标为p的站点 其行驶路程为:2ap+2b(x-p)=2bx+2(a-b)p 要使行驶路程最短: 1、a-b>0时,选择p较小的站点,且a-b越大优先选 2、a-b<0时,选择p较大的站点,且a-b越小优先选 3、a=b时,结果与p无关,固定为2bx */ const int N=1e5+10; ll n,m,x; ll ans; struct sta{//站点 ll p,c; }s[N];//s数组存站点 struct car{//货车 ll a,b; }c[N];//c数组存货车 bool cmp1(sta x,sta y){ return x.p<y.p; } bool cmp2(car x,car y){ return (x.a-x.b)>(y.a-y.b); } int main(){ cin>>n>>m>>x; for(int i=1;i<=n;i++){//站点 cin>>s[i].p>>s[i].c; } for(int i=1;i<=m;i++){//货车 cin>>c[i].a>>c[i].b; ans+=2*c[i].b*x; //答案先加上固定值 } sort(s+1,s+n+1,cmp1);//站点数组按p升序排序 sort(c+1,c+m+1,cmp2);//货车数组按a-b降序排序 int left=1,right=n;//最左和最右站点 for(int i=1;i<=m;i++){//从前往后遍历货车1到m if(c[i].a-c[i].b>0){//a-b>0的货车 ans+=2*(c[i].a-c[i].b)*s[left].p; s[left].c--;//当前站点容纳车辆数-1 if(s[left].c==0) left++;//如果当前站点容纳车辆数减为0,切换到下个站点 } } for(int i=m;i>=1;i--){//从后往前遍历货车m到1 if(c[i].a-c[i].b<0){//a-b<0的货车 ans+=2*(c[i].a-c[i].b)*s[right].p; s[right].c--;//当前站点容纳车辆数-1 if(s[right].c==0) right--;//如果当前站点容纳车辆数减为0,切换到下个站点 } } cout<<ans; return 0; }
- 1
Information
- ID
- 110
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By