http://acm.sgu.ru/problem.php?contest=0&problem=114
求带权中位数，一开始也不知道带权中位数是什么。求带权中位数代码里用的是先排序再用二分查找（好像二分查找写得很恶心。。）。求带权中位数还有线性时间的算法，等过几天再写写吧。WA了很多次，都是在二分查找的边界处理上
#include <stdio.h>
#include <stdlib.h>
typedef struct tagCity {
float x;
long long p;
} City;
int cmp(const void* a, const void* b) {
City* pa = (City*)a, *pb = (City*)b;
if (pa->x < pb->x) {
return -1;
} else if (pa->x > pb->x) {
return 1;
} else {
return 0;
}
}
int main(void) {
int n;
scanf ("%d", &n);
City cities[15000];
int i;
for (i = 0; i < n; ++i) {
scanf ("%f%I64d", &cities[i].x, &cities[i].p);
}
qsort(cities, n, sizeof(cities[0]), cmp);
for (i = 1; i < n; ++i) {
cities[i].p += cities[i-1].p;
}
long long mid = cities[n-1].p / 2;
i = 0;
int j = n-1, m;
while (i <= j) {
m = (i+j)/2+1;
if (i == j) {
m = i;
break;
}
if (cities[m-1].p>=mid) {
j=m-1;
} else if (cities[m].p<mid) {
i=m+1;
} else {
break;
}
}
printf ("%.5f\n", cities[m].x);
return 0;
}