【POJ 1723】 SOLDIERS

【题目链接】

           http://poj.org/problem?id=1723

【算法】

          中位数

【代码】

         

#include <algorithm>  
#include <bitset>  
#include <cctype>  
#include <cerrno>  
#include <clocale>  
#include <cmath>  
#include <complex>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <ctime>  
#include <deque>  
#include <exception>  
#include <fstream>  
#include <functional>  
#include <limits>  
#include <list>  
#include <map>  
#include <iomanip>  
#include <ios>  
#include <iosfwd>  
#include <iostream>  
#include <istream>  
#include <ostream>  
#include <queue>  
#include <set>  
#include <sstream>  
#include <stdexcept>  
#include <streambuf>  
#include <string>  
#include <utility>  
#include <vector>  
#include <cwchar>  
#include <cwctype>  
#include <stack>  
#include <limits.h> 
using namespace std;
#define MAXN 10010

struct Pos
{
        int x,y;
} a[MAXN];

int i,ans,n;

inline bool cmpx(Pos a,Pos b)
{
        return a.x < b.x;
}
inline bool cmpy(Pos a,Pos b)
{
        return a.y < b.y;
}

int main() 
{
        
        scanf("%d",&n);
        for (i = 1; i <= n; i++) scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+n+1,cmpx);
        for (i = 1; i <= n; i++) a[i].x = a[i].x - i + 1;
        sort(a+1,a+n+1,cmpy);
        for (i = 1; i <= n; i++) ans += abs(a[i].y - a[(n+1)>>1].y);
        sort(a+1,a+n+1,cmpx);
        for (i = 1; i <= n; i++) ans += abs(a[i].x - a[(n+1)>>1].x);
        printf("%d
",ans);
        
        return 0;
    
}