ICPC 2023 Nanjing R L 题 Elevator

$\text{[Problem Discription]}$

来源：洛谷。侵权则删。

$\text{[Analysis]}$

贪心。优先运送楼层高的货物，在能装下的情况下尽量多装。

因为运送货物的代价仅和最高楼层的货物有关，假设一次运送货物时的最高楼层为 $h$，那么无论你剩下的货物楼层高还是低，代价都是 $h$ 是固定的。

既然这样，我们应该优先把尽量高的货物都运送上去，剩下来的都是高度低的货物，后面的代价会减小。

排序后，从楼层高的货物开始装填，能装下就装下。注意处理特殊情况：即电梯剩余空间只有 $1$，但贪心需要装大小为 $2$ 的货物时是装不下的。但是既然电梯空间还有剩余，就不应该浪费，应该找到下一个大小为 $1$ 的货物。

指针来回的挪动可能会导致 T，因此按 $w=1,2$ 把货物分成两批，分别用一个指针来维护。这样可以保证时间复杂度为 $O(n)$。

总时间复杂度 $O(n\log n)$，主要瓶颈在于排序。

但是，并没有做完!

这道题对代码能力的要求还是很高的。代码中有非常多容易出错的地方！相信这个贪心还是很多选手都能想到的，但是能不能写出来也是一个重要的问题。

具体的细节看代码中的注释。

$\text{Code}$

const int N=1e5+100;struct Marchandise{int amount,high;Marchandise(int a=0,int h=0){amount=a;high=h;}bool operator < (const Marchandise &c) const{return high>c.high;}
}a[N],b[N];//w=1,2 的分别存 int n,r1,r2;
ll lim,ans;int OZDY(){n=read();lim=read();ans=r1=r2=0;for(int i=1;i<=n;i++){int c=read(),w=read(),f=read();if (w==1) a[++r1]=(Marchandise){c,f};else b[++r2]=(Marchandise){c,f};}sort(a+1,a+r1+1);sort(b+1,b+r2+1);a[r1+1]=(Marchandise){0,0};b[r2+1]=(Marchandise){0,0};//没有这两行应该也没问题int l1=1,l2=1;ll remain=lim;while (l1<=r1&&l2<=r2){if (b[l2].high>=a[l1].high&&remain!=1){//楼层高的优先int tmp=(int)min((ll)b[l2].amount,remain>>1);if (remain==lim) ans+=b[l2].high;remain-=(tmp<<1);b[l2].amount-=tmp;//到这一行，remain 和 amount 至少一个被清零。if (!b[l2].amount){l2++;if (remain==0) remain=lim;continue;//注意一定要 continue，不然可能就直接进入下一个 if，开始装填 l2+1 了，但 l2+1 不一定是下一个装填的货物（可能是 l1，但不可能是 l2+2）。}if (l2>r2) break;if (remain==0){ans+=1ll*b[l2].high*((b[l2].amount<<1)/lim);//注意括号b[l2].amount%=(lim>>1);if (!b[l2].amount){l2++;remain=lim;}else{ans+=b[l2].high;remain=lim-(b[l2].amount<<1);l2++;}}}else{if (remain==1){a[l1].amount--;remain=lim;//这句话别忘了if (!a[l1].amount) l1++;continue;}//电梯剩余空间为 1 特殊处理int tmp=(int)min((ll)a[l1].amount,remain);if (remain==lim) ans+=a[l1].high;remain-=tmp;a[l1].amount-=tmp;if (!a[l1].amount){l1++;if (remain==0) remain=lim;//都恰好拿完 continue;}if (l1>r1) break;if (remain==0){ans+=1ll*a[l1].high*(a[l1].amount/lim);a[l1].amount%=lim;if (!a[l1].amount){l1++;remain=lim;}else{ans+=a[l1].high;remain=lim-a[l1].amount;l1++;}}}} //每进入循环一次，要么 l1 加一要么 l2 加一，保证时间复杂度if (remain==0) remain=lim; //注意维护关键变量（其实出循环后 remain 应该不会为 0，但是维护一下以免出乱子，反正不费事）while (l2<=r2){if (remain==1) remain=lim;//只剩下 w=2 的货物了，剩余的 1 空间没用了int tmp=(int)min((ll)b[l2].amount,remain>>1);//下面的语句几乎就是复制过来的。if (remain==lim) ans+=b[l2].high;remain-=(tmp<<1);b[l2].amount-=tmp;if (!b[l2].amount) l2++;//这里不需要 continue 了，因为下一个装的一定是 l2+1if (l2>r2) break;if (remain==0){ans+=1ll*b[l2].high*((b[l2].amount<<1)/lim);b[l2].amount%=(lim>>1);if (!b[l2].amount){l2++;remain=lim;}else{ans+=b[l2].high;remain=lim-(b[l2].amount<<1);l2++;}}}while (l1<=r1){int tmp=(int)min((ll)a[l1].amount,remain);if (remain==lim) ans+=a[l1].high;remain-=tmp;a[l1].amount-=tmp;if (!a[l1].amount) l1++;if (l1>r1) break; if (remain==0){ans+=1ll*a[l1].high*(a[l1].amount/lim);a[l1].amount%=lim;if (!a[l1].amount){l1++;remain=lim;}else{ans+=a[l1].high;remain=lim-a[l1].amount;l1++;}}}//虽然代码看着很长，但是最主要的四段几乎就是复制粘贴，修改一些小细节printf("%lld\n",ans);return n;
}int main(){int T=read();while (T--) OZDY();return 0;
}