제목: 조금 큰 블루 브리지

8860 단어 푸른 다리 진제
제목:조금 큰 열
직렬은 사전 순서에 따라 비교할 수 있다.예: abcd가 abdc보다 작음
만약 한 꿰미를 정해 놓고 알파벳을 흐트러뜨리고 다시 배열하면 많은 다른 꿰미를 얻을 수 있다. 이 꿰미 중 한 꿰미가 딱 정해진 꿰미가 조금 크다.과학적으로 말하자면, 그것은 이미 알고 있는 열보다 큰 모든 열 중 가장 작은 열이다.너의 임무는 바로 이 좀 큰 꼬치를 구하는 것이다.
예를 들어 입력 문자열: abfxy 프로그램은 출력해야 합니다: abfyx
그리고 예를 들어 입력 문자열:ayyxxff 프로그램은 출력해야 한다:fafxxyy
데이터 크기 규약: 입력한 문자열은 1000글자를 넘지 않습니다.
특례: 이미 알고 있는 직렬이 모든 재구성 직렬에서 가장 크면, 읽은 직렬을 그대로 출력합니다.
자원 규약: 최대 메모리 사용량(VM 포함) <256M CPU 사용량 <1000ms
next_mutation은 여기서 정상적인 방법과 사고방식을 말하지 않았다. ayyxxff의 예를 들어 뒤에서 앞으로 자모보다 큰 것을 찾고 y가 a보다 큰 것을 찾았다. 그리고 그 위치(y)부터 뒤로 a보다 조금 큰 것을 찾았다. 주의는 조금 크다. 첫 번째 f를 찾았다. 그리고 f와 a를 교환해서 fyyxxaf가 되었다. 그리고 f(원래 a의 위치) 다음의 꼬치sort를 찾았다.
#include
#include
#include
#include
using namespace std;
int main()
{
	char s[1005],temp[1005],book[500]={0},k=0;
	scanf("%s",s);
	int i,j,len=strlen(s);
	strcpy(temp,s);
	sort(temp,temp+len);
	map<char,int> m;
	for(i=0;i<len;i++)
	{
		if(book[temp[i]]==0)
		{
			book[temp[i]]=1;
			m[temp[i]]=k;
			k++;
		}
	}
	for(i=len-1;i>0;i--)
	{
		if(s[i]>s[i-1])
		{
			for(j=i;j<len;j++)
			{
				if(m[s[j]]==m[s[i-1]]+1)
				{
					char t=s[j];
					s[j]=s[i-1];
					s[i-1]=t;
					sort(s+i,s+len);
					printf("%s",s);
					return 0;
				}	
			}
		}
	}
	return 0;
} 

좋은 웹페이지 즐겨찾기