パスワードstl関数の応用注意mapの使用2012-10-7


A.パスワード
アナンは暗号解読の達人だ.周波数分析を通じて、多くのパスワードを解読した彼は敵軍のメッセージをキャプチャした.このメッセージにはN個の数字(<=C)があり、彼はこれらの数字を並べ替えて、常用数字を常用しない数字の前に並べ替えたいと思っている.例えば、Xの出現回数はYより多く、XはYの前にある.両者の出現回数が同じであれば、彼らの元のメッセージの前後順に決める.
INPUT
複数組の入力があり、各組の入力の最初の行には2つの整数が入力され、N(1≦N≦1 000)--メッセージの長さ、C(1≦C≦1 000 000 000 000 000 000)、次はN個の数字で表されるメッセージであり、各数字はC以下である.
OUTPUT
グループごとに1行出力し、N個の数をソートします.
input
output
5 2 2 1 2 1 2 9 3 1 3 3 3 2 2 2 1 1                                   9 77 11 33 11 77 54 11 25 25 33
2 2 2 1 1 1 1 1 3 3 3 2 2 2 11 11 11 33 33 25 25 77 54                                                  
この問題はmap関数でマッピングを構築する注意マッピングを構築する~~
#include<stdio.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
           int num;   //     
           int sum;   //     
           int rank;  //          
           } a[1100];
int cmp(node a,node b)
{
     if(a.sum==b.sum) return a.rank<b.rank;    
     else {
             return a.sum>b.sum;
          }
}           
           
           
int main()
{
      int n,m,i,num,j,edge;
      while( scanf("%d %d",&n,&m)!=EOF )
      {
           memset(a,0,sizeof(a));
           j=1;
           map<int,int>my;
           map<int,int>::iterator k;
           for(i=1;i<=n;i++)
             {
               scanf("%d",&num);
               if( my.find(num)==my.end()  ){     //         
                                  a[j].num=num;   //   
                                  a[j].rank=j;    //          
                                  a[j].sum++;     //    
                                  my[num]=j++;    //    
                                 }
               else {
                     a[my[num]].sum++;
                    } 
             }     
           edge=j-1;
           sort(a+1,a+1+edge,cmp);
           int flag=0; 
           for( i=1; i<=edge; i++)  //     
           {
              if(flag==0){printf("%d",a[i].num);a[i].sum--;flag=1;}  //       
              if(flag!=0) {
                   for(j=1;j<=a[i].sum;j++)
                     printf(" %d",a[i].num);                                  
                   }
           }
           printf("
"); } }