글 읽기 - 대체 반례가 무엇일까요....

rottoy 4년 전 0

n번째 수를 기준으로 l만큼의 왼쪽과 오른쪽의 최솟값을 저장하고 대략 O(N)시간만에 알고리즘을 작성했습니다...

왼쪽 최소값을 저장하는 배열은 L이고, 오른쪽 최소값을 저장하는 배열은 D, 정답 배열은 m입니다.

도대체 뭐 때문에 안되는지 모르겠습니다..

#include<iostream>
#include<queue>
using namespace std;
int L[5000001];
int a[5000001];
int m[5000001];
int d[5000001];
int min(int a, int b) { return a < b ? a : b; }
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, l;
	cin >> n >> l;
	for (int i = 1; i <= n; i++) { 
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) { L[i] = 1e9 + 1; d[i] = 1e9 + 1; }
	m[1] = a[1];
	for (int i = 2; i <= l; i++) {
		if (a[i] < m[i - 1])m[i] = a[i];
		else m[i] = m[i - 1];
	}
	int st = l;
	while (true) {
		if (st > n)break;
		L[st] = a[st];
		d[st + 1] = a[st + 1];
		for (int i = st - 1; i >= st-l+1; i--) {
			if (a[i] < L[i + 1]) L[i] = a[i];
			else L[i] = L[i + 1];
		}
		for (int i = st+2; i <= st+l-1; i++) {
			if (a[i] < d[i - 1])d[i] = a[i];
			else d[i] = d[i - 1];
		}
		for (int i = st; i <= st+l-1; i++) {
			if(i==st)
				m[i] = min(L[i-l+1],a[i]);
			else
				m[i] = min(L[i - l + 1], d[i]);
		}
		st += l;
	}
	//for (int i = 1; i <= n; i++) cout << L[i] << " ";
	//cout << endl;
	//for (int i = 1; i <= n; i++) cout << d[i] << " ";
	//cout << endl;
	for (int i = 1; i <= n; i++) cout << m[i] << " ";
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

대체 반례가 무엇일까요....

rottoy 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말