题解：P11376 [GESP202412 六级] 运送物资

xinxin2022 · 2024-12-12 19:17:51 · 题解

简单题。

考虑贪心，显然去 A 市多的车的起始点尽量靠左，去 B 市多的车起点尽量靠右。

那么将起始点升序排序，车按照 a-b 升序排序，令去 A 地次数多的车从左向右分配起始点，令去 B 地次数多的车从右向左分配起点。

若次数相等，则起始点在哪里行驶距离都一样，无需特殊处理。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,ans,cnt;
struct node{
    int a,b;
}car[100005];
struct node2{
    int p,c;
}station[100005];
bool cmp(node2 x,node2 y){
    return x.p<y.p;
}bool cmp2(node x,node y){
    return x.a-x.b>y.a-y.b;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++) cin>>station[i].p>>station[i].c;
    for(int i=1;i<=m;i++) cin>>car[i].a>>car[i].b;
    sort(station+1,station+1+n,cmp);
    sort(car+1,car+1+m,cmp2);
    //处理去A地次数多的车
    for(int i=1,j=1;car[i].a>=car[i].b;i++){
        if(cnt==station[j].c){
            cnt=0;
            j++;
        }
        ans+=2*car[i].a*station[j].p+2*car[i].b*(x-station[j].p);
        cnt++;
    }
    cnt=0;
    //处理去B地次数多的车
    for(int i=m,j=n;car[i].a<car[i].b;i--){
        if(cnt==station[j].c){
            cnt=0;
            j--;
        }
        ans+=2*car[i].a*station[j].p+2*car[i].b*(x-station[j].p);
        cnt++;
    }
    cout<<ans;
    return 0;
}