2436.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2436 on 2007-01-04 at 12:51:15 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

class Data {
public:
	int v, sum;
	Data(int cv, int cs) : v(cv), sum(cs) {}
	bool operator >(const Data& d) const { return v > d.v; }
};

int main()
{
	int n;
	priority_queue< Data, vector<Data>, greater<Data> > Q;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		while(!Q.empty()) Q.pop();
		for(int i = 0; i < n; i++) {
			int a; scanf("%d", &a);
			Q.push(Data(a, 0));
		}
		for(int i = n; i > 1; i--) {
			Data a = Q.top(); Q.pop();
			Data b = Q.top(); Q.pop();
			Q.push(Data(a.v+b.v, a.sum+b.sum+a.v+b.v));
		}
		int m = Q.top().sum, pos = 0;
		for(int i = 1; i < n; i++) pos = (pos+m)%(i+1);
		printf("%d\n", pos+1);
	}
	
	return 0;
}