题解：P12187 [蓝桥杯 2025 省 Python A/Java A/研究生组] 原料采购

· · 题解

P12187 [蓝桥杯 2025 省 Python A/Java A/研究生组] 原料采购

题意

路上有 n 个站点，第 i 个站点有 b_i 个货物，每个货物 a_i 元，距离为 c_i ，单位距离运费为 o ，需要装满容量为 m 的卡车，问最小代价。

思路

妖零圈（省选计划老师）下午在群里说蓝桥杯的题过于经典，过于板子了，所以说质量不高，但是练习 trick 还是好的。

~愣着干什么，报班啊！~

回到正题。

答案为 -1 的情况很简单，就是\sum_{i=1}^{n} b_i < m 。

做题的时候也很容易想到，如果当前选的更优，那么很显然直接替换掉之前选过的不优的即可。没接触过这个技巧的同学可能会无从下手，或者硬暴力看之前哪个选过的可以被替换。

我们可以用一个叫做翻回贪心的 trick 来解决这道题。就是用一个大根堆（优先队列）来存单位价值和数量。

每次弹出不优的，放入更优的即可。

这个时候还差一个关键点，距离。

那我弹出不优的，是不是还要减去他们的距离带来的运费呢?这个时候岂不是很麻烦。（比如当前弹掉了不优秀的，我不优秀的之前的距离是什么？再比如我当前虽然单价更优更便宜，但是加上运费就贵了，那我岂不是白弹了？）

想复杂了

我们发现，物品都是一样的，也就是说我卡车装一个 1 号站点的物品和装一个 2 号站点的物品，除了价钱不一样，剩下都一样。

那么我们可以在更新优先队列结束后去统计价钱。

先给出部分代码。

while(sz(q)){
      pii it=q.top();
      if(it.fi>a[i]){
          q.pop();
          if(b[i]>Used+it.se){
              v-=it.fi*it.se;
              Used+=it.se;
            }else{
                v-=it.fi*(b[i]-Used);
                it.se-=(b[i]-Used);
                Used=b[i];
                if(it.se)q.push(it);break;
              }
        }else break;
    }
  if(Used){
      q.push({a[i],Used});
      v+=a[i]*Used;
  }
    ans=min(ans,v+c[i]*o);

比如说有三次，第一次放入很贵的物品，此时装满。第二次放入很便宜的物品但是运费很贵导致还不如第一次优。第三次放入运费和商品价格都很便宜的物品。

我们直接看最后对 ans 的更新，就是说即便第二次你队列里物品已经从第一次的被换成第二次的了，ans 不优也不会改变，本质上物品是没有被换的。

而接下来假设要被真正替换的话。表面上是第三次的物品替换了第二次的（因为此时由于单价，队列里存的商品实际上是第二次单价低但是运费贵而没被替换的），实际上和第三次的物品替换了第一次没有区别。

然后就可以愉快地切了这道题了。 哦，由于值域范围，初始答案记得设大一些，像我设置成 10^{16} 就第一发喜提了 95pts 。

完整代码

#define rep(i, a, b) for(int i=a;i<=b;i++)
#define sz(x) (int)(x).size()
int m,o,a[100005],b[100005],c[100005],n;
void solve() {
    cin >> n >> m >> o;
    int ss = 0;
    rep(i, 1, n)cin >> a[i] >> b[i] >> c[i], ss += b[i];
    if (ss < m) {
        cout << -1;
        return;
    }
    priority_queue<pii > q;
    int now = 0, ans = 4e18, v = 0;
    rep(i, 1, n) {
        if (now + b[i] <= m) {
            now += b[i];
            q.push({a[i], b[i]});
            v += a[i] * b[i];
            continue;
        } else {
            if (now < m) {
                q.push({a[i], m - now});
                v += a[i] * (m - now);
                b[i] -= (m - now);
                now = m;
            }
            int Used = 0;
            while (sz(q)) {
                pii it = q.top();
                if (it.fi > a[i]) {
                    q.pop();
                    if (b[i] > Used + it.se) {
                        v -= it.fi * it.se;
                        Used += it.se;
                    } else {
                        v -= it.fi * (b[i] - Used);
                        it.se -= (b[i] - Used);
                        Used = b[i];
                        if (it.se)q.push(it);
                        break;
                    }
                } else break;
            }
            if (Used) {
                q.push({a[i], Used});
                v += a[i] * Used;
            }
            ans = min(ans, v + c[i] * o);
        }
    }
    cout << ans;
}