ACM (UVa) : 10954



#include <stdio.h>
#include <algorithm>
using namespace std;

int partition (long a [], int p, int r)
{
	int x = a [r];
	int i = p - 1;

	for (int j = p; j < r; j++) {
		if (a &#91;j&#93; <= x) {
			i++;
			swap (a &#91;i&#93;, a &#91;j&#93;);
		}
	}

	swap (a &#91;i + 1&#93;, a &#91;r&#93;);

	return i + 1;
}

void quick_sort (long a &#91;&#93;, int p, int r)
{
	if (p < r) {
		int q = partition (a, p, r);
		quick_sort (a, p, q - 1);
		quick_sort (a, q + 1, r);
	}
}

int main ()
{
    long n, a &#91;5010&#93;, i, sum, key;

    while (scanf ("%ld", &n)) {

        if (n == 0)
        return 0;

        for (i = 0; i < n; i++)
        scanf ("%ld", &a &#91;i&#93;);

        quick_sort (a, 0, n-1);
        sum = 0;

        while (n > 1) {
            sum += a [0] + a [1];
            key = a [0] + a [1];
            //a [1] = 100010;

			for (i = 2; i < n; i++)
				a &#91;i - 2&#93; = a &#91;i&#93;;
			i = n - 3;
			while (a &#91;i&#93; > key) {
				a [i + 1] = a [i];
				i--;
			}
			a [i + 1] = key;

            n--;
        }
        printf("%ld\n", sum);
    }

    return 0;
}


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