题解：P13962 [ICPC 2023 Nanjing R] 电梯

· · 题解

前言

本篇题解的解题方法为：贪心。

题目大意

:::info[题目] 有 n 组包裹需要被配送。第 i 组共有 c_i 个包裹，每个包裹的重量为 w_i（w_i 等于 1 或 2），并且需要被送到第 f_i 层。

有一台电梯，每趟能运送总重量不超过 k（k 是偶数）的包裹。电梯会从地面层出发，渐渐移动到这一趟所有包裹的目标楼层的最高层 h，最后返回地面层。这一趟运送将消耗 h 单位的电能。

更正式地，令 (w, f) 表示一个重量为 w，且目的地为第 f 层的包裹。一个由包裹组成的多重集合（一种可能含有重复元素的集合）\mathbb{P} 能在同一趟被运送，若 \sum\limits_{(w, f) \in \mathbb{P}} w \le k。这一趟运送将消耗 \max\limits_{(w, f) \in \mathbb{P}} f 单位的电能。

求将所有包裹运送到目的地最少一共需要多少单位的电能？

请注意，每一趟运送的包裹可以来自不同组，每一组包裹也可以分成多趟运送。您可以认为一共有 \sum\limits_{i=1}^n c_i 个包裹需要被运送，只不过一些包裹可能有相同的重量以及相同的目的地。 :::

说人话就是把一些包裹移到楼上，有 n 组包裹，第 i 组有 c_i 个包裹，重量为 w_i（w_i 等于 1 或 2），需要运输到楼层 f_i，每趟能运送总重量不超过 k（k 是偶数）的包裹，代价为这些包裹中最大的楼层，问最小的代价。

解题思路

看到这道题大概就知道是一道贪心，具体的思路如下：

考虑到每一组包裹可以分离，每一个包裹的运输不会影响后续的操作，即无后效性，所以我们可以对所有的包裹以楼层为关键字总大到小排序，每一次尽可能多的拿走包裹，每趟成本由最高楼层决定，所以把低楼层包裹塞进高楼层未满趟是零成本的；贪心先用完免费容量，再开新趟并尽量装满，必然让高成本楼层对应趟数最少。

这样子我们就从局部最优变成了全局最优，得到了一个贪心思路。

代码实现

排序可以写一个结构体和自定义排序函数，用 sort 进行排序。

贪心部分的是实现也不是很难，可以看下面的代码理解。

综上，我们的这道题就完成了！

最后，记得开 long long！

AC 代码

#include <bits/stdc++.h>
using namespace std;

struct bag{
    long long c,w,f;
};

bag hh[100005];

bool cmp(const bag &a,const bag &b){return a.f>b.f;}

void solve(){
    long long n,k,ans=0,s=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>hh[i].c>>hh[i].w>>hh[i].f;
    sort(hh+1,hh+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(hh[i].c*hh[i].w<=s) s-=hh[i].c*hh[i].w,hh[i].c=0;
        else{
            long long tmp=ceil((hh[i].c*hh[i].w-s)/1.0/k);
            s+=tmp*k-hh[i].c*hh[i].w;
            hh[i].c=0;
            ans+=hh[i].f*tmp;
        }
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        solve();
        cout<<'\n'; 
    }
    return 0;
}

record

后记

这是本蒟蒻的第 7 篇题解，求过。

给个赞再走呗！