U142792移动箱子（北大附中2021新春公开赛T3）

题意

有n列箱子，其中有些是宝箱、其他是空箱。每一秒钟你可以选择以下操作执行：

1. 将第i列最上面的一个箱子移动到第j列的最上面；
2. 如果第i列最上面的一个箱子是宝箱，将其打开取出宝物，之后这个箱子消失；

你也可以理解成 n个栈，每次操作移动某个栈顶元素、或者删除某个位于栈顶的宝箱。

请问如果想打开所有宝箱，最少需要的操作次数。

对于 $100\%$ 的数据，保证 $1\le T\le 5, 1 < n\le 10^5, 0\le h\le 10^9, \sum{m}\le5\times 10^5$。

思路

初步想法

首先做几次样例，可以发现本题好像可以使用贪心的思想。

建议读者先自己模拟几遍样例过程，找找规律再接着往下看。

通过模拟样例，我们大概可以初步想到，先搬空一列，之后每一个上方的空箱，就把它挪到这个空列中。

为什么这个贪心是对的呢？仔细想想，如果把所有的空箱来回来回挪很明显是不如只挪一列。

tips

上方只是一些初步想法，下面我们可以完善一些。

• 每一列只有到最底下的一个宝箱和它的上方是有意义的

• 选择挪走的宝箱挪动次数是 $2*\text{空箱次}$，同时还要加 $n$，注意空箱是从最底下的宝箱以上算的。

• 其余的列只需要挪走有意义部分的长度次就可以做到了。

代码

#include<cstdio>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const ll MAXN=1e8;
ll T,n,h,m,a;
int main(){
    scanf("%lld",&T);
    for (int t = 1; t <=T ; ++t) {
        scanf("%lld",&n);
        ll num=0,min_imp=0,ans=0,min_v=0x3f3f3f3f;
        for (int i = 1; i <=n ; ++i) {
            scanf("%lld%lld",&h,&m);
            ll Min=0x3f3f3f3f3f3f;
            for (int j = 1; j <=m ; ++j) {
                scanf("%lld",&a);
                Min= min(Min,a);
            }
            if(((h-Min+1)-m)<min_v){
                min_v=(h-Min+1)-m;
                ans-=num;
                ans+=min_imp;
                num=((h-Min+1)-m)*2+m;
                min_imp=(h-Min+1);
                ans+=num;
            }else{
                ans+=(h-Min+1);
            }
            //cout<<num<<" "<<min_imp<<" "<<ans<<endl;
        }
        cout<<ans<<endl;
    }
    return 0;
}