UVa : 10327 (Flip Sort)



// http://uva.onlinejudge.org/external/103/10327.html

Notes : 
1. N <= 1000. That means u can solve the prb in O(n^2) time i.e, u can use nested loop 

2. u don't need to exchange between elements in array 

3. go through all the elements and find out how many elements after that are bigger than this

input : 
10
1 2 5 4 7 8 5 4 1 3
10
4 5 5 4 5 2 1 4 6 4
10
10 1 2 3 4 5 6 7 8 9

output : 
Minimum exchange operations : 20
Minimum exchange operations : 20
Minimum exchange operations : 9


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
using namespace std;

int main ()
{
    int n;

    while ( scanf ("%d", &n) != EOF ) {
        int a [1000 + 5];

        for ( int i = 0; i < n; i++ )
            scanf ("%d", &a [i]);

        int cnt = 0;

        for ( int i = 0; i < n; i++ ) {
            for ( int j = i + 1; j < n; j++ )
                if ( a [i] > a [j] ) cnt++;
        }

        printf ("Minimum exchange operations : %d\n", cnt);
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s