首页 > 代码库 > 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; }