HDu 4312 Meeting point-2(4級)

6024 ワード
Meeting point-2
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 866    Accepted Submission(s): 472
Problem Description
It has been ten years since TJU-ACM established. And in this year all the retired TJU-ACMers want to get together to celebrate the tenth anniversary. Because the retired TJU-ACMers may live in different places around the world, it may be hard to find out where to celebrate this meeting in order to minimize the sum travel time of all the retired TJU-ACMers.
It's an opportunity to show yourself in front of your predecessors!
There is an infinite integer grid at which N retired TJU-ACMers have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time.
Eg: (x,y) can be reached from (x-1,y), (x+1,y), (x, y-1), (x, y+1), (x-1,y+1), (x-1,y-1), (x+1,y+1), (x+1,y-1).
Finding a common meeting place which minimizes the sum of the travel time of all the retired TJU-ACMers.
 
Input
The first line is an integer T represents there are T test cases. (0For each test case, the first line is an integer n represents there are n retired TJU-ACMers. (0 
Output
For each test case, output the minimal sum of travel times.
 
Sample Input 

   
   
   
   

    
    
    
    4
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
6
0 0
2 0
-5 -2
2 -2
-1 2
4 0
5
-5 1
-1 3
3 1
3 -1
1 -1
10
-1 -1
-3 2
-4 4
5 2
5 -4
3 -1
4 3
-1 -2
3 4
-2 2

 
Sample Output 

   
   
   
   

    
    
    
    20
15
14
38

    
    
    
    
 
     
 
      Hint 
     
 In the first case, the meeting point is (0,2); the second is (0,0), the third is (1,-1) and the last is (-1,-1)

 
Author
TJU
 
Source
2012 Multi-University Training Contest 2
 
Recommend
zhuyuanchen520
考え方:
max{|x|,|y|}=1/2(|x+y|+|x-y|);
したがってxをx+y,y->x-yに変える.マンハッタンの距離を計算することができます.
x,yからある点までのマンハッタン距離は別々に計算できるので,ある点を中心とした値球が最小であればよい.
           前処理,kx[x]ある点xを中心としたすべてのx距離と,ky[]は同じである.kx[i]=kx[i-1]+(i-n+i)*(f[i].x-f[i-1].x);
もう一つの犬の糞の方法は、推測+列挙で、運が良ければ、データが非常に強くなければ過ごせます.
それをX,Y順に並べ替えて、答えは中間段で点を取るのですが、いくつ挙げるべきでしょうか??これは問題なので、少し犬の糞があります.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mm=2e5+9;
class node
{
public:
    __int64 x,y;
    int id;
} f[mm];
bool cmpx(node a,node b)
{
    return a.x<b.x;
}
bool cmpy(node a,node b)
{
    return a.y<b.y;
}
__int64 kx[mm],ky[mm];
__int64 sum;
__int64 aabs(__int64 x)
{
    if(x<0)return -x;
    return x;
}
int main()
{
    int cas;__int64 n,xx,yy;
    while(~scanf("%d",&cas))
    {
        while(cas--)
        {
            scanf("%I64d",&n);
            for(int i=0; i<n; ++i)
                {
                scanf("%I64d%I64d",&xx,&yy);
                f[i].x=xx-yy;f[i].y=xx+yy;
                }
            sort(f,f+n,cmpx);
            kx[0]=0;
            for(int i=0; i<n; ++i)
            {
                kx[0]+=aabs(f[i].x-f[0].x);
                f[i].id=i;
            }
            for(__int64 i=1; i<n; ++i)
                kx[i]=kx[i-1]+(i-n+i)*(f[i].x-f[i-1].x);
            //for(int i=0;i<n;++i)
            //cout<<" "<<kx[i]<<" ";puts("");
            sort(f,f+n,cmpy);
            ky[0]=0;
            for(int i=0;i<n;++i)
            ky[0]+=aabs(f[i].y-f[0].y);
            for(__int64 i=1;i<n;++i)
               ky[i]=ky[i-1]+(i+i-n)*(f[i].y-f[i-1].y);
            //for(int i=0;i<n ;++i)
            //cout<<" "<<ky[i]<<" ";puts("");
            sum=6e18;
            for(int i=0;i<n;++i)
            { //cout<<f[i].id<<" "<<i<<" "<<kx[f[i].id]<<" "<<ky[i]<<" "<<ky[i]+kx[f[i].id]<<endl;
              if(sum>ky[i]+kx[f[i].id])sum=ky[i]+kx[f[i].id];
            }
           printf("%I64d
",sum/2);
        }
    }
    return 0;
}

///250以下は基本的に間違っていて、以上は基本的に超えています.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;
const int maxn = 1000010;

pair<int,int> p[maxn];

int abs1(int a) {
    return a<0?-a:a;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
           scanf("%d %d",&p[i].first,&p[i].second);
        sort(p,p+n);
        int l = max(n/2-250,0);
        int r  = min(n/2+250,n);
        __int64 ans = 999999999999999LL;
        //cout << ans << endl;
        for(int i=l;i<r;i++)
        {
            __int64 tmp = 0;
            for(int j=0;j<n;j++)
               tmp += max(abs1(p[j].first-p[i].first),abs1(p[j].second-p[i].second));
            ans = min(ans,tmp);
        }
        printf("%I64d
",ans);
    }
    return 0;
}
/*
3
10 88
0 1
0 5
1
0 2
0 0
1
1
1
*/
形態学演算では腐食,膨張,開演算,閉演算を行う.
3.ansibleの使用とモジュール化の深い解析