2013年10月10日 星期四

UVa 484 - The Department of Redundancy Department

Problem link

Keyword: ad hoc, search

Algorithm:

Scan through all numbers.
If it exists, then add 1 to the specific cell storing the number of existence.
If not, then add a new cell to the list.
Then you can print out all the numbers and their frequencies.

Code:
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
class node
{
public:
    node( int );
    int val, freq;
    bool operator==( node );
};
node::node( int v )
{
    val = v;
    freq = 1;
}
bool node::operator==( node a ) { return a.val == val; }

int main()
{
    vector<node> all;
    vector<node>::iterator it;
    int n;

    while( scanf( "%d", &n ) != EOF )
        if( ( it = find( all.begin(), all.end(), node( n ) ) ) == all.end() )
            all.push_back( node( n ) );
        else
            ++(*it).freq;
    for( it = all.begin(); it != all.end(); ++it )
        printf( "%d %d\n", (*it).val, (*it).freq );

    return 0;
}

沒有留言:

張貼留言