洛谷P3522 TEM-temperature

单调队列+阅读理解

简化题意。

找到一个最长的区间使得区间每个点的r要大于该点之前的点的l。

然后可以用单调队列维护单调递减的l。最后尺取法O(n)枚举所有区间并取最大值。

单调队列可以快速找某个位置左右两侧比他大（或小）的数的位置

#include <bits/stdc++.h>//题目意思就是找到一段最长的区间使得

#define N 1010111

using namespace std;

int n, l[N], r[N], maxn;

deque <int> q;

int main()

{

	scanf("%d", &n);

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

		scanf("%d%d", &l[i], &r[i]);

	q.push_back(1);			 //q存下标

	int now = 0;//now要设为零

	for	(int i = 2; i <= n; i++)

	{

		while (!q.empty() && r[i] < l[q.front()])//如果l[队头]大于r[i]的话则不行,等于则不需更新

		{

			now = q.front();

			q.pop_front();

		}

		if (q.size())

		maxn = max(i - now, maxn);//now是满足当前情况下的，最左边的数

		while (q.size() && l[i] >= l[q.back()])//队列里满足l单减

			q.pop_back();

		q.push_back(i);

	}

	printf("%d", maxn);

	return 0;

}

/*

6

6 10

1 5

4 8

2 5

6 8

3 5

*/

巴特西

洛谷P3522 TEM-temperature

最新文章

热门文章