洛谷P3434 [POI2006]KRA-The Disks题解

此乃本蒟蒻做出的第一道蓝题 感觉好简单

感觉就是黄题难度

题目转送门

正文开始

前置思路

维护一个序列 (f)，使 (f_i=min(r_i,f_{i-1}))，(f_1=r_1)

这样 (f_i) 就表示 (min(r_1,r_2,r_3cdots r_i))

(f_i) 也就是 (r_1)~(r_i) 最窄的管子的直径。

对于每个盘子，在放入管子的时候（能放的情况）都是由上到下（落下）进入管道，在遇到盘子阻挡或比自己窄的管子时才会停下来。

代码思路

知道了从第 (1) 层到第 (i) 层（没有盘子阻挡的最下层）最小的直径，从下往上找，直到找到最小直径能放下第 (j) 个盘子为止。

一共只用循环一遍，时间复杂度是 (O(n))

从下往上找，找到一个满足条件的就换下一个（指盘子），直到最上方（塞不下了）。

如果塞不下了就输出 (0)。

代码

#include<iostream>
#include<queue>
using namespace std;
int a[300005];
int main()
{
	int n,m,ans,k;
	cin>>n>>m>>a[1];
	for(int i=2;i<=n;i++)
		cin>>a[i],a[i]=min(a[i],a[i-1]);//上方最小值
	k=n;//k用来存储目前是第几层
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		while(x>a[k--]);//找到能塞下的一层
		if(k==0)//塞不下了
		{
			cout<<0;
			return 0;
		}
	}
	cout<<k+1;//最后一次多减了一，补回来
	return 0;
}

完结撒花 (。・∀・)ノ花花花