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+1
		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++;
			}
		}
	}
	
	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;
}