글 읽기 - 반례좀 찾아주실수 있을까요? ㅠㅠ 스택 문제입니다..

hata676 3년 전 0

논리상 오류가 없는거같은ㄷ네 도무지 어떤게 반례인지 ㅁ르겠습니다 ㅠㅠㅠ

도움 부탁드립니다..

#include <bits/stdc++.h>
using namespace std;

int N, h, ans;
stack <pair<int,int>> st;
int arr[80001];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for(int i=N; i>=1; i--){
		cin >> h;
		arr[i] = h;
	}

	for(int i=1; i<=N; i++){
		while(!st.empty() && st.top().first < arr[i])
			st.pop();
		if(st.empty()){
			ans += i-1;
			cout << i - 1 << " ";
		} else {
			ans += i - st.top().second - 1;
			cout << i - st.top().second - 1 << " ";
		}
		st.push(make_pair(arr[i],i));
	}

	cout << "\n" << ans;
}

spearkkk 2달 전 0

스택에는 항상 높이가 높은 빌딩부터 낮은 빌딩으로 내림차순으로 유지하고 있고...

스택에 새로운 빌딩을 넣기 전에 스택에 있는 빌딩들의 크기를 카운팅하면 됩니다.

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

문제

문제

출처

ICPC

반례좀 찾아주실수 있을까요? ㅠㅠ 스택 문제입니다..

hata676 3년 전 0

spearkkk 2달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말