글 읽기 - 2142 정돈된 배열 질문입니다

portableangel 8년 전 0

각 행마다 (오른쪽 원소의 값 - 왼쪽 원소의 값) 중 가장 큰 값, 작은 값을 전처리한 뒤

O(n^2)으로 모든 행에 대해 최악의 경우에도 조건을 만족하는지 브루트 포스로 체크하는 코드입니다.

혹시 어디에 오류가 있는지 알 수 있을까요?

#include <stdio.h>
#include <algorithm>

using namespace std;

int a[500][500];
int mind[500], maxd[500];

int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		int n, m;
		scanf("%d %d",&n,&m);
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++)
				scanf("%d",&a[i][j]);
		}
		if(n<1 || m<1 || n>500 || m>500) while(1);
		if(n<2 || m<2) { puts("YES"); continue; }
		for(int i=0;i<n;i++) {
			int mn=a[i][0], mx=a[i][0];
			int mndif=a[i][1]-a[i][0], mxdif=a[i][1]-a[i][0];
			for(int j=1;j<m;j++) {
				mndif=min(mndif,a[i][j]-mx);
				mxdif=max(mxdif,a[i][j]-mn);
				mn=min(mn,a[i][j]); mx=max(mx,a[i][j]);
			}
			mind[i]=mndif; maxd[i]=mxdif;
		}
		bool ok=true;
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				if(mind[i]<maxd[j]) {
					ok=false; break;
				}
			}
			if(!ok) break;
		}
		puts(ok?"YES":"NO");
	}
}

koosaga 8년 전 1

각 행마다 (오른쪽 원소의 값 - 왼쪽 원소의 값) 중 가장 큰 값, 작은 값을 전처리한 뒤

-> 행마다 저 값을 최대 / 최소화하는 원소가 다르기 때문에 의미가 없습니다.

portableangel 8년 전 0

감사합니다. 어디가 문제인지 알았습니다.. ㅠㅠ

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

문제

문제

출처

ICPC

2142 정돈된 배열 질문입니다

portableangel 8년 전 0

koosaga 8년 전 1

portableangel 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말