1 solutions

  • 0
    @ 2025-11-27 11:59:01

    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