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

Bh_hurter · 2024-12-11 22:11:12 · 题解

P11376 题解

题目传送门

题意分析

题意很简单，要把 m 辆车放到 n 个车站中，其中每个车站 p 在 p_i 的位置，可以存下 c_i 辆车。目标是找到一种方案，使得所有的车送完物资后总行驶里程最小。

不难想到，一辆车每往 A 地和 B 地各送一次物资，路程 S=2 \times p+2 \times (x-p) =2 \times (p+x-p) =2 \times x ，即走了两趟全程。所以不管这辆车的起始站在哪里，每往 A 地和 B 地各送一次物资，路程都是 2 倍的全程。

不免想到贪心。既然一辆车每往 A 地和 B 地各送一次物资，路程都是 2 倍的全程，那么这辆车至少会走 a_i 和 b_i 中较小的那个倍数的全程。所以只用考虑 a_i 或 b_i 多出来的部分就行了。

先把所有站点排个序，然后将 a_i 大的车从离 A 地最近的站点开始放，每次先放当前 a_i-b_i 最大的车。同样从离 B 地最近的车站开始放 b_i 大的车，每次先放当前 b_i-a_i 最大的车。可以在输入时将这两种车分开存，处理更加方便。

AC Code

下面是本人考场代码，给大家献丑了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
const int N=1e5;
struct node {
    int a,b;
}cara[N+5],carb[N+5];//cara存a[i]较大的车，carb存b[i]较大的车
struct point {
    int p,c;
}st[N+5];//每个车站信息
int n,m,px;
int cnta=0,cntb=0;
ll ans=0;
bool cmp(node x,node y) {
    return abs(x.a-x.b)<abs(y.a-y.b);
}
bool cmq(point x,point y) {
    return x.p<y.p;
}
int main() {
    cin>>n>>m>>px;
    for(int i=1; i<=n; i++) {
        cin>>st[i].p>>st[i].c;
    }
    sort(st+1,st+1+n,cmq);
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        if(x>=y) cara[++cnta].a=x,cara[cnta].b=y;
        else carb[++cntb].a=x,carb[cntb].b=y;
    }
    sort(cara+1,cara+1+cnta,cmp);//采用倒着排序，后面每次放完一辆车后只需cnta--便可删除这个车
    sort(carb+1,carb+1+cntb,cmp);//同理
    int l=1,r=n;
    while(cnta>0) {
        if(cnta<st[l].c) {//小心下表越界
            while(cnta>0) {
                ans=ans+2ll*cara[cnta].a*st[l].p+2ll*cara[cnta].b*(px-st[l].p);
                cnta--;//放完这辆车了，删掉
            }
        } else {
            for(int i=1; i<=st[l].c; i++) {
                ans=ans+2ll*cara[cnta].a*st[l].p+2ll*cara[cnta].b*(px-st[l].p);//计算答案
                cnta--;//放完这辆车了，删掉
            }
            l++;//下一车站
        }
    }
    while(cntb>0) {
        if(cntb<st[r].c) {//小心下表越界
            while(cntb>0) {
                ans=ans+2ll*carb[cntb].a*st[r].p+2ll*carb[cntb].b*(px-st[r].p);
                cntb--;//放完这辆车了，删掉
            }
        } else {
            for(int i=1; i<=st[r].c; i++) {
                ans=ans+2ll*carb[cntb].a*st[r].p+2ll*carb[cntb].b*(px-st[r].p);//计算答案
                cntb--;//放完这辆车了，删掉
            }
            r--;//下一车站
        }

    }
    cout<<ans;//输出
    return 0;
}