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

· · 题解

\color{blue}{\texttt{[Analysis]}}

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

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

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

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

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

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

::::warning[但是，并没有做完]{open} 这道题对代码能力的要求还是很高的。代码中有非常多容易出错的地方！

相信这个贪心还是很多选手都能想到的，但是能不能写出来也是一个重要的问题。

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

\color{blue}{\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;
}