紫书 例题8-9 UVa 1451 （数形结合）

这道题用了数形结合， 真的牛逼， 完全想到不到还可以这么做

因为题目求的是平均值， 是总数除以个数， 这个时候就可以联系

到斜率， 也就是说转化为给你一堆点， 让你求两点之间的最大斜率

要做两个处理

（1）去掉上凸点， 因为上凸点是无论如何都不会为最优解的

（2）去掉之后每两个点之间的斜率是单调递增的， 这个时候要求切点。

切点即最大斜率， 所以就枚举终点， 然后找该终点对应的最大斜率

（也就是找到切点）， 然后更新答案。

#include<cstdio>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112345;

int sum[MAXN], p[MAXN], n, L;

char s[MAXN];

inline int compare_average(int x1, int x2, int x3, int x4)  //比较斜率

{

	return (sum[x2]-sum[x1-1]) * (x4-x3+1) - (sum[x4]-sum[x3-1]) * (x2-x1+1);

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d%d%s", &n, &L, s+1);   //s+1从位置一开始输入

		sum[0] = 0;

		REP(i, 1, n + 1) sum[i] = sum[i-1] + s[i] - '0';

		int ansL = 1, ansR = L, i = 0, j = 0;   //i到j这个区间代表去掉之后留下的有用的点

		REP(t, L, n + 1)

		{

			while(j - i > 1 && compare_average(p[j-2], t-L, p[j-1], t-L) >= 0) j--; //去掉上凸点

			p[j++] = t - L + 1;

			while(j - i > 1 && compare_average(p[i], t, p[i+1], t) <= 0) i++;  //去掉切点之前的点

			int c = compare_average(p[i], t, ansL, ansR);  //更新答案

			if(c > 0 || c == 0 && t - p[i] < ansR - ansL)

			{

				ansL = p[i];

				ansR = t;

			}

		}

		printf("%d %d\n", ansL, ansR);

	}

	return 0;

}