*[topcoder]TaroFriends
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
http://community.topcoder.com/stat?c=problem_statement&pm=13005
好题。最暴力是试验2^n种跳法。然后有从结果入手，那么最终的左右是i, j，有n^2种（每种4个跳法），然后花O(n)的时间去验证。
最后的正解比较有意思，就是观察到必须向里跳才有意义，那么只有RRRRRR...LLLLLL这种形式的才满足，于是遍历这个R和L的分界点就行了。
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std; class TaroFriends {
public:
int getNumber(vector <int> coordinates, int X) {
int ret = 1000000000;
int N = coordinates.size();
sort(coordinates.begin(), coordinates.end());
for (int i = 0; i <= N; i++) {
int minPos = 1000000000;
int maxPos = -1000000000;
for (int j = 0; j < N; j++) {
int pos = 0;
if (j < i) { // R
pos = coordinates[j] + X;
} else { // L
pos = coordinates[j] - X;
}
minPos = min(pos, minPos);
maxPos = max(pos, maxPos);
}
ret = min(ret, maxPos - minPos);
}
return ret;
}
};
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |