좋 은 욕심

제목:
카드 게임
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1088    Accepted Submission (s): 341 Problem Description 샤 오 밍 은 최근 에 집에 서 심심 해서 재 미 있 는 게임 을 발 명 했 습 니 다. 게임 도 구 는 N 장 으로 겹 쳐 진 카드 입 니 다. 카드 마다 숫자 가 있 습 니 다. 숫자의 범 위 는 0 ~ 9 입 니 다. 게임 규칙 은 다음 과 같 습 니 다. 먼저 맨 위 에 있 는 카드 를 꺼 내 서 책상 위 에 놓 은 다음 에 맨 위 에 있 는 카드 를 찾 습 니 다.책상 위 에 카드 서열 이 있 는 맨 오른쪽 이나 맨 왼쪽 에 놓 으 세 요.카드 N 장 을 모두 테이블 위 에 올 려 놓 으 면 테이블 위의 카드 N 장 이 하나의 수 를 이룬다.이 숫자 는 선도 0 이 있어 서 는 안 된다. 즉, 가장 왼쪽 카드 의 숫자 는 0 이 될 수 없다 는 것 이다.게임 의 목 표 는 이 수 를 최소 화 하 는 것 이다.  지금 당신 의 임 무 는 샤 오 밍 을 도와 프로그램 을 써 서 이 최소 수 를 구 하 는 것 입 니 다.  Input 첫 줄 은 T 그룹 테스트 데이터 가 있 음 을 나타 내 는 숫자 T 입 니 다.그리고 아래 에 T 줄 이 있 습 니 다. 줄 마다 0 ~ 9 만 들 어 있 는 문자열 로 N 장 이 겹 쳐 진 카드 를 표시 하고 가장 왼쪽 숫자 는 맨 위 에 있 는 카드 를 표시 합 니 다.[Technical Specification] T < = 1000 1 < = N < = 100 Output 은 각 그룹의 테스트 데이터 에 대해 한 줄 에서 얻 을 수 있 는 최소 수 를 출력 하 십시오.  Sample Input 3 565 9876543210 9876105432   샘플 출력 556 1234567890 1678905432 사고방식:      처음에는 너무 가 벼 워, 속도 두 드 려, 속도 와, 아이고!부 끄 럽 습 니 다. 먼저 생각 하 는 것 은 욕심 입 니 다. 한 가 지 는 우리 가 생각 할 수 있 습 니 다. 가장 높 은 숫자 가 작 을 수록 이 숫자 는 작 습 니 다. 먼저 우 리 는 첫 번 째 를 고려 합 니 다. 우 리 는 가장 작은 것 을 찾 고 가장 작은 것 을 찾 습 니 다. 그 다음 에 가장 작은 것 은 첫 번 째 입 니 다. 가장 작은 것 은 가장 뒤에 있 을 것 입 니 다. 그리고 순서 가 바 뀌 지 않 고 가장 작은 것 을 찾 으 면 이해 할 수 있 습 니 다. 그런데 왜 가장 뒤에 있 습 니까?생각해 보 니 뒤에 있 으 면 그 가 나중에 꺼 냈 다 는 것 을 설명 하고 나중에 꺼 낸 것 이 가장 작은 것 은 틀림없이 맨 앞 에 있 는 사람 이다. 만약 에 그 가 맨 앞 에 있 는 사람 이 라면 앞 에 있 는 사람 이 숫자 를 더 할 수 없 기 때문에 뒤의 것 은 바로 맨 뒤의 것 이다. 이렇게 해서 처음으로 우 리 는 답 의 첫 번 째 숫자 와 맨 뒤의 데 이 터 를 찾 았 다.
주의 하 세 요. 첫 번 째 는 0 이 될 수 없습니다. 두 번 째 단 계 는 앞의 두 번 째 데이터 와 마지막 꼴찌 두 번 째 데이터 입 니 다. 세 번 째 단 계 는..................................................

#include
#include

#define N 500
#define INF 1000000000

int num[N];
int ans[N];
char str[N];

int main ()
{
   int t ,l ,r ,n ,tt ,i;
   scanf("%d" ,&t);
   while(t--)
   {
      scanf("%s" ,str);
      n = strlen(str);
      for(i = 1 ;i <= n ;i ++)
      num[i] = str[i- 1] - 48;
      l = 0 ,r = n + 1;
      tt = n;            
      while(tt)
      {
         int min_num = INF;
         int min_id = -1;
         for(i = tt ;i >= 1 ;i --)
         {
            if(min_num > num[i])
            {
               if(tt == n && !num[i]) continue;
               min_num = num[i];
               min_id = i;
            }
         }
         ans[++l] = min_num;
         for(i = tt ;i > min_id ;i --)
         ans[--r] = num[i];
         tt = min_id - 1;
      }
      for(i = 1 ;i <= n ;i ++)
      printf("%d" ,ans[i]);
      puts("");
   }
   return 0;
}