HDU 4550カードゲーム【欲張り】

転送ドア:HDU 4550
カードゲーム
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description小明は最近家にいて退屈で、そこで彼は1種の面白いゲームを発明して、ゲームの道具はN枚重ねたカードで、1枚のカードの上にすべて1つの数字があって、数字の範囲は0~9で、ゲームの規則は以下の通りです:まず一番上のカードをテーブルの上に置いて、それから毎回一番上のカードを取って、テーブルの上に置いてあるカードのシーケンスの一番右か一番左です.N枚のカードを全てテーブルの上に置くと、テーブルの上のN枚のカードが1つの数になります.この数に先頭0があるわけではありません.つまり、一番左のカードの数字は0ではありません.ゲームの目標はこの数を最小限に抑えることです.今あなたの任務は明ちゃんにプログラムを書いて、この最小数を求めることです.
Inputの最初の行は数Tであり、Tグループのテストデータがあることを示す.そして下にT行があり、各行は0~9のみの文字列で、N枚重ねのカードを表し、一番左の数字は一番上のカードを表しています.[Technical Specification]T<=1000 1<=N<=100 Output各テストデータについて、得られる最小数を1行に出力してください.Sample Input 3 565 9876543210 9876105432
Sample Output 556 1234567890 1678905432
この問題は長い間考えていたが,料理の真実は.最初は初期カードより小さいものを左に置いて、頭を更新して、大きいものを右に置いて尾を更新して、明らかに間違っていて、その中に多くの間違いがあって、バグを直して半日やっと多くのネット上で探したサンプルを過ぎて、結果はやはりwaで、考え直してやっと考えが間違っていることに気づいた.それから右から左に探して、最初のゼロではない最小数を探して、それを先頭にして、その位置の右は必ず最後になって、左は小さいから大きいまで順番に並べばいいと思っています.渡すとやはりwa...最後に彼が貪欲であることに気づいて、この考えを最適化することを優先します.
問題解:右から左へ探して、最初のゼロでない最小数を探して、それを先頭にして、その位置の右側は必ず最後で、左は上述の操作を繰り返します.最初の最小値を探します(この場合は0にすることができます.先頭は0ではないと判断されています).先頭の後ろに配置され、右側も最後に、左側で操作を繰り返します.このようにして、すべての数が並べ替えられるまで往復します.結果を出力します.
ACコード:

#include
 #include
 #include
 #include
 #include
 #include
 using namespace std;
 const int N=110;
 char str[N];
 int main()
 {
 	int T;
 	scanf("%d", &T);
 	while (T--)
 	{
 		scanf("%s", str);
     int len=strlen(str);
     int k=0,minn=10;
     for(int i=len-1;i>=0;i--)
     {
       if(str[i]<minn+'0'&&str[i]!='0')
       {
         minn=str[i]-'0';
         k=i;
       }
     }
     queue<char> q;
     q.push(str[k]);
     stack<char> s;
     for(int i=len-1;i>k;i--)
     {
       s.push(str[i]);
     }
     int t1=q.size(),t2=s.size();
     while(t1+t2<len&&k>0)
     {
       int tmp=k-1;
       for(int i=tmp-1;i>=0;i--)
       {
         if(str[i]<str[tmp]) tmp=i;
       }
       q.push(str[tmp]);
       t1++;
       for(int i=k-1;i>tmp;i--)
       {
         s.push(str[i]);
         t2++;
       }
       k=tmp;
     }
     while(!q.empty())
     {
       printf("%c",q.front());
       q.pop();
     }
     while(!s.empty())
     {
       printf("%c",s.top());
       s.pop();
     }
     printf("
");
 	}
   return 0;
 }