[topcoder]TheConsecutiveIntegersDivOne

http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278
우선 맨 해 튼 거리 최소 치 문 제 를 기억 하면 1 차원 상황 이 떠 오 르 고 점 이 중위 수 에 나타 나 는 것 이 가장 작다.여기 서도 네 개의 점 이 중위 자리 에 나타 나 는 것 이 가장 작 다 는 것 을 증명 할 수 있다.
문제 풀이 에 서 는 줄 이 고 싶 은 절대 치 를 최소 화 하 는 모든 상황 을 탐색 하 는 것 이다.
내 코드 는 좀 못 생 겼 지만 지 나 쳤 다.

#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;

	}

};