POI2006 KRA-The Disks

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Thu Nov 01 08:54:32 CST 2018

In Category: NoCategory

Description：

一个框，告诉你每一层的宽度。向下丢给定宽度的木块。木块会停在卡住他的那一层之上，异或是已经存在的木块之上。询问丢的最后一个木块停在第几层。

$1\leqslant n\leqslant 300000$

Solution：

求一个前缀 $\min$ ，然后双指针求出每次落在的位置即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 300010

int l[MAXN];

int d[MAXN];

int minv[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)l[i] = rd();

	for(int i = 1;i <= m;++i)d[i] = rd();

	minv[0] = 0x3f3f3f3f;

	for(int i = 1;i <= n;++i)minv[i] = min(minv[i - 1],l[i]);

	int cur = n;

	for(int i = 1;i <= m;++i)

	{

		while(cur > 0 && minv[cur] < d[i])--cur;

		if(cur == 0)

		{

			cur = -1;

			break;

		}

		--cur;

	}

	cout << cur + 1 << endl;

	return 0;

}

In tag: 技巧-双指针

wjh15101051