poj-2231

//264K	47MS	C++
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAX = 10005;

long long cowLocation[10005];

int cmp(const void * a, const void * b) {
	return *((long long *)a) - *((long long *)b);
}

long long cowNum;

long long sum;

long long curLeftSum;
long long curRightSum;

long long leftCowNum;
long long rightCowNum;

int main() {
	while(scanf("%lld", &cowNum) != EOF) {
		sum = 0;
		curLeftSum = 0;
		curRightSum = 0;
		for (long long i = 0; i < cowNum; i++) {
			scanf("%lld", &cowLocation[i]);
		}
		qsort(cowLocation, cowNum, sizeof(long long), cmp);
		for (long long i = 1; i < cowNum; i++) {
			curRightSum += cowLocation[i] - cowLocation[0];
			// printf("V %lld\n", cowLocation[i]);
		}
		sum += (curRightSum + curLeftSum);

		long long prevCowId = 0;
		long long curCowId = 1;
		leftCowNum = 0;
		rightCowNum = cowNum - 1;
		while(rightCowNum) {
			// printf("%d\n", rightCowNum);
			long long varyDistance = cowLocation[curCowId] - cowLocation[prevCowId];
			curRightSum -= rightCowNum*(varyDistance);
			rightCowNum--;
			leftCowNum++;
			curLeftSum += leftCowNum*(varyDistance);
			sum += (curRightSum + curLeftSum);
			// printf("AA %lld %lld %lld %lld %lld %lld\n",
			 	// sum, curRightSum, curLeftSum,
			 	// rightCowNum, leftCowNum, varyDistance);
			curCowId++;
			prevCowId++;		
		}
		printf("%lld\n", sum);
	}
}

虽然分类是排序，但是排序在这里只是一个预处理的角色，真正的思路是递推，和编程之美上的坐电梯那道题有点像，其实就是DP啦。

如果知道在某个位置的cow K， 其左边cow的数量是leftCowNum， 右边cow数量是 rightCowNum, 其他cow的位置也都知道，就可以求出，

K与其他cow的距离的和，两部分： 与左边cow的距离的和 leftCowSum, 和 右边cow的距离的和rightCowSum， 两者相加就是K带来的volume，

而要求 K后面一位的cow K+1， 只需在原来的leftCowNum和 rightCowNum进行 加减一定量的大小(细节在code里面，也很简单)既可以 递推出来，就这样遍历一遍cow，将每个cow的volume相加，就是最后的结果.