글 읽기 - 반례좀 부탁드립니다

p_ce1052 3년 전 0

그리디하게 최댓값을 앞으로 끌고 올 수 있으면 가져온 후 남은 이동 횟수에 대해 뒤의 배열을 구성하고 최댓값을 앞으로 가져올 수 없으면 앞의 배열에 대해서 최대한 사전순으로 크게 만들고 남은 횟수로 최댓값을 앞으로 이동시킨 뒤 종료하였습니다. 반례가 뭔지 모르겠습니다

#include<bits/stdc++.h>
using namespace std;
vector<int>arr;
int f(int l,int r,int s){
	if(!s) return 0;
	if(l>=r) return s;
	int mx = 0;
	for(int i=l; i<=r; i++) mx = max(mx,arr[i]);
	int idx;
	for(int i=l; i<=r; i++){
		if(arr[i]==mx){
			idx = i;
			break;
		}
	}
	if(idx==l) return f(l+1,r,s);
	else{
		if(idx-l<=s){
			for(int i=idx; i>l; i--) swap(arr[i],arr[i-1]);
			s-=(idx-l);
			return f(l+1,r,s);
		}
		else{
			int remain = f(l,idx-1,s);
			if(!remain) return 0;
			for(int i=idx; i>l; i--){
				remain--;
				swap(arr[i],arr[i-1]);
				if(!remain) break;
			}
			return 0;
		}
	}
}
int main(){
	int n;
	cin>>n;
	arr = vector<int>(n);
	for(auto &a:arr) cin>>a;
	int s;
	cin>>s;
	f(0,arr.size()-1,s);
	for(int i=0; i<arr.size(); i++) cout<<arr[i]<<" ";
}

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

문제

문제

출처

ICPC

반례좀 부탁드립니다

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말