学步园

SGU_114

    这个题目乍看起来没什么思路，但如果随便挑一个点作为station，然后分别左右移动一下看看移动之后能够减少多少不满同时又会增加多少不满，思路便瞬间有了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 15010
int N, x[MAXD], p[MAXD], r[MAXD];
long long int A[MAXD];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return x[*p] - x[*q];
}
void solve()
{
int i, j, k, min, max, mid;
for(i = 1; i <= N; i ++)
        scanf("%d%d", &x[i], &p[i]);
for(i = 1; i <= N; i ++)
        r[i] = i;
    qsort(r + 1, N, sizeof(r[0]), cmp);
    A[0] = 0;
for(i = 1; i <= N; i ++)
        A[i] = A[i - 1] + p[r[i]];
    min = 1, max = N + 1;
for(;;)
    {
        mid = (max + min) / 2;
if(mid == min)
break;
if(A[mid] <= A[N] / 2)
            min = mid;
else
            max = mid;
    }
if(A[mid] <= A[N] / 2)
        printf("%d.00000\n", x[r[mid + 1]]);
else
        printf("%d.00000\n", x[r[mid]]);
}
int main()
{
while(scanf("%d", &N) == 1)
    {
        solve();
    }
return 0;
}