uva 1451 - Average(数形结合）

题目链接：uva 1451 - Average

题目大意：给出n和L，表示有一个长度为01组成的字符串，要求找出子串长度不小于L，且含有1的平均值最大，长度尽量小。

解题思路：树形结合，将字符串的每个位置对应成xOy坐标上的点，那么平均指即为两点之间的斜率。

然后维护一个相邻两点斜率递增的一个集合q（即凸点集），然后后面枚举的点只需要在这个集合中找切点即为该点满足题意的最优斜率。注意比如从1~5，有3个‘1’，除数不是5-1=4，要注意它占了1，2，3，4，5，5个位置，所以除数是5，所以枚举两点的时候要注意。

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

const int N = 1e5+10;
int n, L;

struct point {
	int x, y;
	point() { x = y = 0; }
	point(int x, int y) {
		this->x = x; this->y = y;
	}
}p[N], q[N];

struct line {
	point p0, p1;
	line() {}
	line(point a, point b) {
		p0 = a; p1 = b;
	}
	bool operator > (const line& c) {
		return (p1.y - p0.y) * (c.p1.x-c.p0.x) > (p1.x - p0.x) * (c.p1.y - c.p0.y);
	}
	bool operator == (const line& c) {
		return (p1.y - p0.y) * (c.p1.x-c.p0.x) == (p1.x - p0.x) * (c.p1.y - c.p0.y);
	}
	bool operator >= (const line& c) {
		return *this > c || *this == c;
	}

	line operator = (const line& a) {  
		p0 = a.p0; p1 = a.p1;  
		return *this;  
	}  
	int len() {
		return p1.x - p0.x;
	}
};

void init () {
	char str[N];
	scanf("%d%d%s", &n, &L, str);

	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (str[i-1] == '1') c++;
		p[i].x = i; p[i].y = c;
	}
}

void solve () {
	int l = 0, r = -1;
	line Max(p[0], p[L]);

	for (int i = L; i <= n; i++) {
		int u = i - L;
		while (l < r && line(q[r-1], p[u]) >= line(q[r], p[u])) r--;
		q[++r] = p[u];
		while (l < r && line(q[l+1], p[i]) >= line(q[l], p[i])) l++;
		line t(q[l], p[i]);
		if (t > Max || ((t == Max) && t.len() <  Max.len() )) {
			Max = t;
		}
	}
	printf("%d %d\n", Max.p0.x+1, Max.p1.x);
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		solve();
	}
	return 0;
}