1070. 结绳(25)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp (const void * a, const void * b) {
	return *(int*)b - *(int*)a;
}

int main(int argc, char * argv[]) {
	int N;
	scanf("%d", &N);
	int ans[N];
	for (int i = 0; i < N; ++i) {
		scanf("%d", ans + i);
	}
	qsort(ans, N, sizeof(int), cmp);
	for (int i = N - 1; i >= 1; --i) {
		int j = ans[i], k = i;
		while (j > ans[k - 1] && k >= 1) {
			ans[k] = ans[k - 1];
			k--;
		}
		ans[k] = j;
		ans[i - 1] += ans[i];
		ans[i - 1] /= 2;
	}
	printf("%d", ans[0]);
	return 0;
}