首页 > 代码库 > [topcoder]TheConsecutiveIntegersDivOne
[topcoder]TheConsecutiveIntegersDivOne
http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278
首先，如果记得曼哈顿距离最小值那个问题，会想起一维的情况可证，点出现在中位数那里是最小的。这里也可证明，四个点，出现在中位数位置是最小的。
题解里的做法是，试探所有让某个想减的绝对值最小的情况。
我的代码有点丑，但过了:
#include <vector>#include <algorithm>using namespace std;class TheConsecutiveIntegersDivOne {public: int find(vector <int> numbers, int k) { sort(numbers.begin(), numbers.end()); int d = k / 2; int left = 0; int sumL = 0; for (int i = left; i < left + d; i++) { sumL += numbers[i]; } int sumR = 0; int right = left + d; if (k % 2 == 1) { right++; } for (int i = right; i < right + d; i++) { sumR += numbers[i]; } int result = sumR - sumL - d * d; while (right + d < numbers.size()) { sumL += numbers[left + d]; sumL -= numbers[left]; sumR += numbers[right + d]; sumR -= numbers[right]; result = min(result, sumR - sumL - d * d); left++; right++; } return result; }};
[topcoder]TheConsecutiveIntegersDivOne
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。