- 首页 > it技术 > >
UVa 11300 - Spreading the Wealth
/*
ch1, 例题3
代数分析 + 快速选择
*/
#include
#include
#include using namespace std;
const int MAXN = 1000004;
long long A[MAXN], B[MAXN];
int n;
int part(int x, int y)
{
int i=x-1, j;
long long key = B[y-1];
for(j=x;
j n/2) return get_mid(x, m);
else return get_mid(m+1, y);
}int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
while(scanf("%d", &n) == 1) {
long long tot = 0, m, x1, ans = 0;
for(int i=1;
i<=n;
i++) {
scanf("%lld", &A[i]);
tot += A[i];
}
m = tot / n;
B[0] = 0;
for(int i=1;
i
推荐阅读
