パスワード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関数でマッピングを構築する注意マッピングを構築する~~
アナンは暗号解読の達人だ.周波数分析を通じて、多くのパスワードを解読した彼は敵軍のメッセージをキャプチャした.このメッセージには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("
");
}
}