G6012 [GESP202412 六级] 运送物资 题解

知识点：贪心、排序、重排不等式、整数范围。

解题思路

单车成本整理为2b_i x+2(a_i-b_i)p。先累计常数项，按差值d=a-b排序：非负差值大的优先占靠近A的站，负差值最小的优先占靠近B的站，并扣减容量。

为什么正确

目标中的位置与差值乘积满足重排不等式，较大差值应配较小位置；容量等价于重复位置，排序配对仍最优。

易错点

站点有容量限制，要跳过用尽的站；差值可为负，不能按往返总次数排序。

复杂度

时间O(n log n+m log m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    long long x;
    cin>>n>>m>>x;
    vector<pair<long long,long long>>st(n);
    for(auto &s:st)cin>>s.first>>s.second;
    sort(st.begin(),st.end());
    vector<long long>d;
    long long ans=0;
    for(int i=0;i<m;i++) {
        long long a,b;
        cin>>a>>b;
        ans+=2*b*x;
        d.push_back(a-b);
    }
    sort(d.rbegin(),d.rend());
    int l=0,h=n-1;
    for(long long v:d)if(v>=0) {
        while(st[l].second==0)l++;
        ans+=2*v*st[l].first;
        st[l].second--;
    }
    for(int i=m-1;i>=0;i--)if(d[i]<0) {
        while(st[h].second==0)h--;
        ans+=2*d[i]*st[h].first;
        st[h].second--;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。