Codeforces 394D Physical Education and Buns(暴力）

题目链接：Codeforces 394D Physical Education and Buns

题目大意：给出含有n个数的集合（数的位置可以交换），要求n个数中的每个数进行小于k次的修改（+1或-1），然后该集合可以构成等差递增的序列，要求k尽量小。

解题思路：枚举公差d，默认首项为0，然后遍历集合，维护修改的最大值和最小值（注意有负数的情况，为向下修改），然后去中间值即为该公差下的最优解。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;
int n, num[N];

void solve () {
	int ans = INF, s, d;
	for (int i = 0; i <= 20000; i++) {
		int l = INF, r = -INF;
		for (int j = 0; j < n; j++) {
			r = max(r, i * j - num[j]);
			l = min(l, i * j - num[j]);
		}	
		int tmp = (r - l + 1)/2;
		if (ans > tmp) {
			ans = tmp;
			s = -r + tmp;
			d = i;
		}
	}
	printf("%d\n%d %d\n", ans, s, d);
}

int main () {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &num[i]);
	sort(num, num + n);
	solve();
	return 0;
}

Codeforces 394D Physical Education and Buns(暴力）

原文：http://blog.csdn.net/keshuai19940722/article/details/19674277