POJ 2823 슬라이딩 창 (단조 로 운 대기 열)

http://poj.org/problem?id=2823
G + + 는 TLE 에 주의 하 세 요.
pair < int, int > 배열 로 deque 를 모 의 하면 됩 니 다.
전체 코드:
/*5360ms,19272KB*/

#include<cstdio>
#include<cstring>
#include<utility>
using namespace std;
const int mx = 1000005;

pair<int, int> minq[mx], maxq[mx]; /// first   ,second           
int maxans[mx];
int minhead, mintail, maxhead, maxtail;

void push(int x, int i)
{
	/// minq.push(x)
	if (mintail != minhead)
		while (mintail != minhead && x <= minq[mintail].first) --mintail;
	minq[++mintail] = make_pair(x, i);
	/// maxq.push(x)
	if (maxtail != maxhead)
		while (maxtail != maxhead && x >= maxq[maxtail].first) --maxtail;
	maxq[++maxtail] = make_pair(x, i);
}

int main()
{
	int n, k, i, j = 1, x, cnt = 0;
	scanf("%d%d", &n, &k);
	for (i = 0; i < k; ++i)
	{
		scanf("%d", &x);
		push(x, i);
	}
	printf("%d", minq[minhead + 1].second == 0 ? minq[++minhead].first : minq[minhead + 1].first);
	maxans[cnt++] = (maxq[maxhead + 1].second == 0 ? maxq[++maxhead].first : maxq[maxhead + 1].first);
	for (; i < n; ++i, ++j)
	{
		scanf("%d", &x);
		push(x, i);
		printf(" %d", minq[minhead + 1].second == j ? minq[++minhead].first : minq[minhead + 1].first);
		maxans[cnt++] = (maxq[maxhead + 1].second == j ? maxq[++maxhead].first : maxq[maxhead + 1].first);
	}
	printf("
%d", maxans[0]); for (i = 1; i < cnt; ++i) printf(" %d", maxans[i]); putchar(10); return 0; }

좋은 웹페이지 즐겨찾기