题目

二分好题

首先用二分找最小的绝对值差，对于每个a[i]都两个方向扫一遍，先都改成差满足的形式，然后再找a[k]等于0的情况，发现如果a[k]要变成0，则从他到左右两个方向上必会有两个连续的区间也随之变化，

然后我们有一点K， 使K点=0时，可以分别向左和右影响区间的值。并且影响之后的值一定互为以0为首项，绝对值差为公差的等差数列。

如在在一段范围内K点影响到的值，以后的点一定不会受到影响，然后修改的次数就是该范围的面积，可以用该区间的值的和减去影响影响范围的等差数列。最后用双指针法求出每个K的左右区间端点，枚举第一个符合条件的最小K即可求出答案

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define N 1001011

#define int long long

using namespace std;

int n, m, li, ri, ans, k, nk;

int data[N], a[N], def[N], sum[N], lef[N], rig[N];

bool check(int t)

{

 	int now = 0;

 	for (int i = 1; i <= n; i++)

 		a[i] = data[i];//a[i]是临时数组

 	for (int i = 2; i <= n; i++)

 		if (a[i] - a[i - 1] > t)//使a[i]减小一次，使a[i]满足条件，前后都扫一遍。

 			now += a[i] - a[i - 1] - t, a[i] = a[i - 1] + t;

 	if (now > m) return false;

 	for (int i = n - 1; i >= 1; i--)

 		if (a[i] - a[i + 1] > t)

 			now += a[i] - a[i + 1] - t, a[i] = a[i + 1] + t;

 	if (now > m) return false;

 	for (int i = 1; i <= n; i++)

 	 	sum[i] = sum[i - 1] + a[i];

 	int l = 1;

 	for (int r = 1; r <= n; r++)

 	{//找到左边最后一个受等差数列影响的

 	 	while (l < r && a[l] <= (r - l) * t) l++;//找左边最近的可以满足条件的位置，lef，rig存放的都是位置

	 	lef[r] = l;

 	}

 	int r = n;

 	for (int l = n; l >= 1; l--)

 	{

 	 	while (r > l && a[r] <= (r - l) * t) r--;

 		rig[l] = r;

 	}

// 	for (int i = 1; i <= n; i++)

//	 	printf("%lld %lld %lld\n", sum[i], lef[i], rig[i]);

 	for (int i = 1; i <= n; i++)

 		if ( (now+sum[rig[i]]-sum[lef[i]-1]-t*((i-lef[i])*(i-lef[i]+1)+(rig[i]-i)*(rig[i]-i+1))/2) <= m)//等差数列求和 + 原先的now <= m， 说明此时是最小的k

	 	    {nk = i;return true;}

 	return false;

}

signed main()

{

 	scanf("%lld%lld", &n, &m);

 	for (int i = 1; i <= n; i++)

 		scanf("%lld", &data[i]);

 	int mid = 0;

 	li = 0;

 	ri = 1e9;

 	while (li <= ri)

 	{

 		int mid = (li + ri) >> 1;

 		if (check(mid))

		{

			ans = mid;

			ri = mid - 1;

		}

		else li = mid + 1;

	}

   	printf("%lld %lld", nk, ans);

}

/*

16 7

8 7 6 5 5 5 3 5 5 6 6 7 7 9 7 5 5

*/