[C++知识库]P3434 [POI2006]KRA-The Disks（往管子里放盘子）C/C++

P3434 [POI2006]KRA-The Disks

思路：
首先我们可以建一个数组，保存此位置之前最窄的管子大小。

再从最底下扫一遍，依次看看盘子会卡在哪里；

最后如果最后一个没进去就到顶部，则输出0；

否则输出最后一个卡在哪里。

AC代码：

#include<iostream>
using namespace std;

long long int R1[300010];//管子直径 
long long int R2[300010];//盘子直径
long long int R3[300010];//记录当前位置之前最窄位置的宽度 

int main()
{
	int n,m;
	cin >> n >> m ;
	
	for(int i=1;i<=n;i++)
	{
		cin >> R1[i];
	}
	
	for(int i=1;i<=m;i++)
	{
		cin >> R2[i];
	}
	
	R3[1]=R1[1];//第一个位置之前最窄的就是自己；
	for(int i=2;i<=n;i++)
	{
		if(R3[i-1]<R1[i])R3[i]=R3[i-1];
		else R3[i]=R1[i];
	}
	
	//开始放盘子 
	int f,step=n;//管子从下往上搜索，底下管子下不去，就向上放 
	for(int i=1;i<=m;i++)
	{
		while(R2[i]>R3[step])step--;//当前位置上面有小于盘子直径的，下不去，往上放；
		step--;
		if(step==0){//一直回到最上面都放不下去 
			cout << "0" << endl ;
			return 0; 
		}
	}
	cout << step+1 << endl ;
	return 0;
}