题目链接 : [POI2006]KRA-The Disks
好有既视感啊。。。
注意一下输入输出
输入是从上到下输入箱子的宽度
输出是最上面的积木停在哪一层
即 箱子高度 - 积木高度 + 1
在初始情况下
对于一层 我们只需要它上面所有层中宽度最小的那层
于是维护这样的一个数列
对于一个插入的值 如果它比前一个数小 那么直接插入
否则插入前一个数的值
比如示例数据
（第i + 1行为插入a[i]后的结果）
|
5 |
6 |
4 |
3 |
6 |
2 |
3 |
|
5 |
||||||
|
5 |
5 |
|||||
|
5 |
5 |
4 |
||||
|
5 |
5 |
4 |
3 |
|||
|
5 |
5 |
4 |
3 |
3 |
||
|
5 |
5 |
4 |
3 |
3 |
2 |
|
|
5 |
5 |
4 |
3 |
3 |
2 |
2 |
那怎么找位置呢？
积木停止下落的原因只有两个
1. 该层箱子的宽度小于积木宽度
2. 有积木挡在下面
对于前者 我们可以二分查找 宽度大于等于当前积木的最下层
对于后者 我们可以判断（（上一个积木上面一层）的位置）与 ↑ 找到的层数
取较上层者为答案
w[] = inf;//记得哦！
for(int i = ; i <= n; i++){
scanf("%d", &w[i]);
w[i] = w[i - ] < w[i] ? w[i - ] : w[i];
}//维护数组
int ans = n;
for(int i = ; i <= m; i++){
int x; scanf("%d", &x);
int l = , r = ans;
while(l < r){
int mid = l + ((r + - l) >> );
if(w[mid] < x) r = mid - ;
else l = mid;
} // 二分查找
if(l >= ans) ans--;
else ans = l; //与上次答案对比
if(!ans) break;
}
主体部分