글 읽기 - 추적방법이 잘못된건가요?? 이것도 될 거라 생각했는데..

wiz9243 5년 전 0

이 방법이 뭐때문에 틀렸는지 알고 싶네요.. 반례도 알고 싶구요

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int real[10005];  //  real[i] = j : i번째 스위치의 진짜 번호
int tmp[10005];
int v[10005];     //  v[i] = j : i 번째 스위치와 j 번째 전구가 연결
vector<int> d;       
vector<int> s;    // 실제 전구 번호가 들어감

int main() {
	int n; cin >> n;
	for ( int i = 1; i <= n; i++ ) {
		int a; scanf("%d", &a);
		real[i] = a;
		tmp[a] = i;
	}
	for ( int i = 1; i <= n; i++ ) {
		int a; scanf("%d", &a);
		v[tmp[a]] = i;
	}

	/*
	예제를 예로들면, v[1]=5, v[2]=1, v[3]=3, v[4]=2, v[5]=4 설정 완료
	*/

	for ( int i = 1; i <= n; i++ ) {
		int idx = lower_bound(d.begin(), d.end(), v[i]) - d.begin();
		if ( idx == d.size() ) {
			d.push_back(v[i]);
			s.push_back(real[i]);
		}
		else {
			d[idx] = v[i];
			s[idx] = real[i];
		}
	}

	sort(s.begin(), s.end());
	cout << s.size() << endl;
	for ( int i = 0; i < s.size(); i++ )cout << s[i] << " ";

}

jh05013 5년 전 0

5
1 2 3 4 5
1 5 2 4 3

hkhkhk5452 2년 전 0

덕분에 반례를 찾았어요. 정말 감사합니다

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

문제

문제

출처

ICPC

추적방법이 잘못된건가요?? 이것도 될 거라 생각했는데..

wiz9243 5년 전 0

jh05013 5년 전 0

hkhkhk5452 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말