首页 > 代码库 > Codility上的问题(35) Neon 2014

Codility上的问题(35) Neon 2014

也是比较有意思的题,越来越数学了……不善于做这种题。


如图一个码头有N个木桩,用于拴住船,码头长度是M,可以理解未0到M的线段。有N调船,每条船的一半长度为X,所以船长是2 * X。每个船的中心必须拴在一个木桩上。并且每个木桩只能拴一条船。拴船的绳子长度是船的中心与木桩位置的距离。当然,木桩的位置不能移动,但是船可以自由左右移动。要求船头船尾必须都在码头上(0..M的线段),船也可以看作长度为2 * X的线段,请给每条船指定一个位置让拴船的最长绳子长度最短,求这个最短的绳子长度。如果无法容纳下所有的船,则输出-1。

函数头部是:int solution(vector<int> &R, int X, int M)

其中R的长度为N,表示木桩的位置,木桩位置非递减,X是半船长,M是码头长度。

数据范围:N是[1..100000], M和X是[1..1000000000]。

要求时间复杂度 O(N),空间复杂度O(N)。

分析: 首先如果所有的船的总长度超过M,则显然无解。当然用除法判断防止溢出,但用乘法似乎也没事。剩下就一定有解了。这个题二分也可以做,但是达不到要求的复杂度。

开始我觉得很混乱,写的代码也很乱。后来整理了一下思路:

(1) 首先把船移动到最左边,这样第i(从0开始)条船的中心位置c[i]为 (2 * i + 1) * X

  (2)    现在看怎样把船往右移动,从左到右移动船,第i条船如果向右移动,后面所有的船都要往右移动。

(3) 第(2)步关键看每条船移动多少,因为右边所有的船一起移动只要记录所有船移动量move即可,于是此时第i条船的传心位置是c[i]‘ = c[i] - move,主要看右边船的最小值(后缀最小值),让这个最小值减少的不太多,即当前船位置和右边所有的最小值的平均值作为移动距离。具体来说,如果此时所有的c‘都为负数,那么不用做了。就是当前船c‘是正数的时候,后面那些船的cx‘“预定了”该船应该向右拉的距离,(c‘ + cx‘) / 2,只要不是这个值,就不是最优,但是当前船只能满足一个,又不能向右拉太多(因为其他船还有向右拉的机会,把当前船向右拉多了没用),所以我们就选取了最小的cx‘。一个理由是因为,如果拉更多的话,最小值会变得更差,——这是因为只能朝右拉,当前船得c‘最终是正的,最小船的c‘最终变为负数,拉多了会差,拉少了当前船的c‘比现在大……

代码:

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int center(int X,int i) {
    return ((i << 1) | 1) * X;
}

int solution(vector<int> &R, int X, int M) {
    // write your code in C++11
    int n = R.size();
    if ((M / (X << 1)) < n) {
        return -1;
    }
    vector<int> mini(n);
    for (int i = n - 1; i >= 0; --i) {
        mini[i] = R[i] - center(X, i);
        if (i + 1 < n) {
            mini[i] = min(mini[i], mini[i + 1]);
        }
    }
    int answer = 0, move = 0;
    for (int i = 0; i < n; ++i) {
        int can = ((R[i] - center(X, i) - move) + (mini[i] - move)) / 2;
        if (can > 0) {
            move += min(can, M - X - center(X, n - 1) - move);
        }
        answer = max(answer, abs(R[i] - center(X, i) - move)); 
    }
    return answer;

}