> //G++ RE C++ AC
> #include <cstdlib>
> #include <iostream>
> #include <cstdio>
> #include <ctime>
> #include <cmath>
> 
> using namespace std;
> 
> const int MAX = 10000+100;
> 
> int Rand(int p, int r)
> {
>     srand((unsigned)time(NULL));
>     return p + rand()%(r-p+1);
> }
> 
> void Exchange(int &a, int &b)
> {
>      int tmp = a;
>      a = b;
>      b = tmp;
> }
> 
> int Partition(int a[], int p, int r)
> {
>     int i, j;
> 	int x = a[r];
>     i = p-1;
>     for (j=p; j<r; j++)
>     {
>         if (a[j] <= x)
>         {
>             i++;
> 			if (i != j)
>                 Exchange(a[i], a[j]);   
>         }
>     }
>     Exchange(a[i+1], a[r]);
>     return i+1;
> }
> 
> int RandPartition(int a[], int p, int r)
> {
>     int i = Rand(p, r);
>     Exchange(a[r], a[i]);
>     return Partition(a, p, r);
> }
> 
> int RandSelect(int a[], int p, int r, int i)
> {
>     if (p == r)
>        return a[p];
>     int q = RandPartition(a, p, r);
>     int k = q-p+1;
>     if (i == k)
>        return a[q];
>     else
>        if (i < k)
>            return RandSelect(a, p, q-1, i);
>        else
>            return RandSelect(a, q+1, r, i-k);
> }
> 
> void QuickSort(int a[], int p, int r)
> {
> 	if (p < r)
> 	{
> 		int q = RandPartition(a, p, r);
> 		QuickSort(a, p, q-1);
> 		QuickSort(a, q+1, r);
> 	}
> }
> 
> int x[MAX], y[MAX], N;
> 
> int main(int argc, char *argv[])
> {
>     scanf("%d", &N);
>     int i, sum=0;
>     for (i=0; i<N; i++)
>         scanf("%d%d", &x[i], &y[i]);
> 	QuickSort(x, 0, N-1);
> 	for (i=0; i<N; i++)
> 		  x[i] = x[i] - i;
> 
>     int kx = RandSelect(x, 0, N-1, (N+1)/2);
>     int ky = RandSelect(y, 0, N-1, (N+1)/2);
> 
>     for (i=0; i<N; i++)
>          sum =  sum + abs(y[i]-ky) + abs(x[i]-kx);
> 	printf("%d\n", sum);
>     return EXIT_SUCCESS;
> }
同问，我也遇到这个问题在2388题

• Re:为神马G++就RE， C++却AC (86) jki14 2011-06-17 22:47:58