Codeforces Round #619 (Motarack’s Birthday)

题面

Dark is going to attend Motarack’s birthday. Dark decided that the gift he is going to give to Motarack is an array a of n non-negative integers.
Dark created that array 1000 years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn’t have much time so he wants to choose an integer k (0≤k≤109) and replaces all missing elements in the array a with k.
Let m be the maximum absolute difference between all adjacent elements (i.e. the maximum value of |ai−ai+1| for all 1≤i≤n−1) in the array a after Dark replaces all missing elements with k.
Dark should choose an integer k so that m is minimized. Can you help him?

题意

给一个数列，其中缺少一些数，用-1替代，请填一个数替换掉-1，使得相邻两项之差的绝对值的最大值最小

分析

直接统计空位旁边的数的最大值最小值，取其平均值即可
另外也要考虑到非空位的两数差所以最后处理时遍历整个数组

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
inline int read() {
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
	return x * f;
}
int a[100001];
int maxn,minn;
void work(int i){
	maxn = max(maxn, a[i]);
	minn = min(minn, a[i]);
}

int main() {
	int t = read();
	while (t--){
		minn = 0x3f3f3f3f, maxn = -0x3f3f3f3f;
		memset(a, 0, sizeof(a));
		int n = read();
		for (int i(1); i <= n; i++) {
			a[i] = read();
		}
		for (int i(1); i <= n; i++){
			if (a[i] == -1){
				if (i > 1 && a[i - 1] != -1) work(i - 1);
				if (i < n && a[i + 1] != -1) work(i + 1);
			}
		}
		int k = minn + maxn >> 1;
		int ans = 0;
		for (int i(1); i <= n; i++)
			if (a[i] == -1) a[i] = k;
		for (int i(1); i < n; i++)
			ans = max (ans, abs(a[i] - a[i + 1]));
		printf("%d %d\n", ans, k);
	} 
	return 0;
}

原文地址：http://www.cnblogs.com/cancers/p/16833229.html