Luogu P13962 [ICPC 2023 Nanjing R] 电梯
https://www.luogu.com.cn/problem/P13962
思维难度很小，但是感觉代码很难写。
运送一堆物品，消耗的电能是这堆物品目标层数的最大值，可以认为只有目标层数最大值的物品才会消耗电能，其他的物品就是“免费”的。我们要让电能最小，就是让的省下的电能尽可能多。
那么可以先运送目标层数大的物品，接下来如果还有空间就继续按照目标层数从大到小塞进去。如果塞完之后发现还有 \(1\) 的空间（称之为“\(1\) 单位缝隙”），就找一个目标层数最大的 \(w=1\) 的物品塞进去。
一开始写的时候用优先队列搞了半天然后超时了，后面发现可以直接先按照目标高度排序，然后扫一遍，对于每一个 \(w=2\) 的物品产生的“\(1\) 单位缝隙”开一个变量 ones_gaps 记录，在 \(w=1\) 时看看能不能塞就可以了。因为是按照高度排序的，所以这个新加进去的 \(w=1\) 物品一定不会对塞进去的电梯电能的计算产生影响。以后做模拟时可以用到这种思想。
一开始的代码：https://www.luogu.com.cn/record/249879315
AC 代码：https://www.luogu.com.cn/record/249885494
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=1e5+7;
struct Node
{ll c,w,to;// 按楼层从高到低排序bool operator<(const Node &B) const{return to>B.to;}
}a[N];
int n;
ll k,ans=0;
inline ll Alhaitham()
{ans=0;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i].c>>a[i].w>>a[i].to;sort(a+1,a+n+1);ll remain=0; //当前最近一次电梯趟次的剩余空间ll ones_gaps=0; //无法被重量2利用的“1单位”缝隙数量for(int i=1;i<=n;i++){if(a[i].w==1){if(ones_gaps>0) //有缝隙给你填充进去{ll amount=min(a[i].c,ones_gaps);a[i].c-=amount;ones_gaps-=amount;}if(a[i].c>0&&remain>0) //填补当前趟次的剩余空间{ll amount=min(a[i].c,remain);a[i].c-=amount;remain-=amount;}//如果还有剩余就新开一个电梯if(a[i].c>0){ans+=(a[i].c+k-1)/k*a[i].to;//这一趟产生的剩余空间if(a[i].c%k==0) remain=0;else remain=k-a[i].c%k;}}else //处理w=2{//填补当前趟次的剩余空间if(remain>=2){ll amount=min(a[i].c,remain/2);a[i].c-=amount;remain-=2*amount;}//还有剩就新开一个电梯 if(a[i].c>0){//这1单位空间重量2无法利用if(remain==1){ones_gaps++;remain=0;}ans+=(a[i].c*2+k-1)/k*a[i].to;if(a[i].c*2%k==0) remain=0;else remain=k-a[i].c*2%k;}}}return ans;
}int main()
{
// freopen("neuvillette.in","r",stdin);
// freopen("neuvillette.out","w",stdout);cin.tie(0)->sync_with_stdio(0);int T;cin>>T;while(T--) cout<<Alhaitham()<<'\n';cout.flush();return 0;
}