POJ 1153 SAFE 解题报告

 

资源来源：http://blog.chinaunix.net/u3/105033/index.html

 

一、问题描述

 

详见：

题目大意

Mirko要打开一把迷你保险箱，保障箱由N（2<=N<=100000）个disc组成，每个disc又被分成1000000个segment，每个segment标一个号，从1到1000000。开始时，每个盘的segment编号都是整齐地一层一层叠放在一起的。每个disc有且只有一个hole。每一秒钟，只能朝一个方向转动一个盘一格，为了开锁，所有的hole应该叠放在同一位置。编程找出最少需要多长时间开锁。

比如

以下输入表示有4个盘，每个盘中hole的位置如下面4个数字表示，输出的结果为29

Input

4

9999999

7

16

9999995

output

29

 

二、分析解答

 

将问题转变为：在一个长度为10000000的圆上有n（2<=n<=100000）个点,每个点都有一个坐标值表示该点所在的位置，求一个点，使得该点到其他所有点的距离之和最小，求出该最小值。

首先想到的是遍历这1千万个点，对于每一个点求其他点到该点的距离和，然后选择之1千万个距离和中的最小值作为结果。需要计算1千万的平方次，超时，不可行！容易发现并不需要计算这1千万个点，因为其中很多点的计算结果是一样的。其实只需要计算n次就行了，对于每个点计算其他点到该点的距离和。计算复杂度为O(n²)，因为n最大为10万，用这种方法提交也出现超时。观察后发现，基点从i-1变成i时，并不需要重新计算i点到所有其他点之间的距离，只需要修改一些改变了的距离就可以。用D[i]表示以i点为基点的距离和。

以i点为基点的距离和计算方法如图所示。首先将n个点按位置大小排序，遍历选择n个点作为基点计算距离和。例如下图：选择0点作为基点，计算其对称点s=(P[0]+1000000/2)%1000000，则以0点为基点的距离和D[0]为其他各点到0点的距离之和，1、2、3点计算逆时针到0点的距离，4、5、6计算顺时针到0点的距离。

算法描述

（1）将输入n个数据按从小到大排序。为了计算方便，将n个数据拓展3n个数据，范围从1到30000000，相当于把n个数据分别加上1千万和2千万再加到的后面。

（2）以第n个数为基点按上面方面计算距离和D[n]; result=D[n];

（3）遍历i(n+1<=i<2n),按下面方法D[i-1]计算D[i],若result>D[i],则result=D[i];

(4)输出结果result

 

由D[i-1]计算D[i]的方法：

 

图中右边红色的两点分别是左边两个红色点的拓展点。右边两条虚线S_i-1,S_i分别表示i-1和i点的对称点，P[i-1][phone]/2=S_i-1，

P[i][phone]/2=S_i。ln为S_i-1与S_i之间的第一个点的下标值。D[i-1]就是直线上面的线段之和，D[i]为直线下面线段之和。图中可以看出，D[i]与D[i-1]之间的不同有两部分：一是蓝色线段部分，二是m段i-1与i之间的距离Dis[i-1,i]，观察后得到m=(n-ln+2*i-j)，即得到：

D[i]=D[i-1]-左边蓝色线段和+右边线段长度和+(n-ln+2*i-j)*Dis[i-1,i]

 

三、算法实现

 

#include <stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int P[300000];
int SEG=10000000;
int main()
{
    long n;
    long i;
    long j;
    double result,tempresult;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>P[i];

    }
    sort(P,P+n);
    for(i=0;i<n;i++)
    {
        P[i+n]=P[i]+SEG;
        P[i+2*n]=P[i+n]+SEG;
    }
    tempresult=0;
    int s;
    s=P[n]+SEG/2;
    for(i=n+1;P[i]<=s;++i)
    {
        tempresult+=(P[i]-P[n]);
    }
    int ln=i;
    j=2*n-i;
    for(i=0;i<j;++i)
    {
        tempresult+=(P[n]-P[n-i-1]);
    }
    result=tempresult;
    for(i=n+1;i<2*n;++i)
    {
        s=P[i]+SEG/2;
        for(j=ln;P[j]<=s;j++)
        {
            tempresult+=(P[j]-P[i]);
            tempresult-=(P[i-1]-P[j-n]);
        }
        tempresult+=((n-ln+2*i-j)*(P[i]-P[i-1]));
        ln=j;
        if(result>tempresult)
            result=tempresult;
    }
    printf("%.0f\n",result);
    return 0;
}