题意
有n列箱子，其中有些是宝箱、其他是空箱。每一秒钟你可以选择以下操作执行：
- 将第
i列最上面的一个箱子移动到第j列的最上面； - 如果第
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;
}