题解 P3434 【[POI2006]KRA-The Disks】
oscar
2017-09-27 21:44:19
【POI补全计划#18 POI2006 KRA】
水到随便做的一道题，然而我的做法还是比楼下题解的做法多个log。。。
直觉上二分肯定能过，就没仔细想线性做法
预处理出管道的每个格子上方最小的半径，将该格子的半径设置为最细的那个，位置0的半径设为足够大的数（正确性：通不过上面的部分就到不了这个格子）（作用：方便二分）
然后每次记录上一个盘子掉到的位置x，在0和x之间查找比盘子半径大的最靠下的位置，若查到x则往上摞一个盘子，若查到0则说明后面的盘子都放不进去，其余情况正常处理就好了....
贴代码：
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int MAXN=300010;
int siz[MAXN],n,m;
int main()
{
scanf("%d%d",&n,&m);
siz[0]=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
scanf("%d",&siz[i]);
if(siz[i]>siz[i-1])siz[i]=siz[i-1];
}
int tmp,cur=n;
for(int i=1;i<=m;i++)
{
scanf("%d",&tmp);
int l=0,r=cur;
while(l<r)
{
int mid=(l+r+1)/2;
if(siz[mid]<tmp)r=mid-1;
else l=mid;
}
if(l==cur)cur--;
else cur=l;
if(cur==0)break;
}
printf("%d\n",cur);
return 0;
}
```