uva1451贪心算法，求平均值最大的子序列 博客分类： 算法题

//uva1451，0.07s
//贪心算法，求平均值最大的子序列
//数形结合，求最大斜率
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100005;
int n;
int front[N], s[N];
char c[N];

double aotu(int x1, int x2,int x3, int x4) {
	return (s[x4]-s[x3])*(x2 - x1) - (s[x2] - s[x1])*(x4 - x3);
}

int main()
{
	int i,T,L,rear,a,b,res1,res2; 
	//double t,best;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n,&L);
		scanf("%s", &c);
		if (n == L) {
			printf("1 %d\n", n);
			continue;
		}
		s[0] = 0;
		for (i = 1; i <= n; i++) {
			s[i] = s[i - 1] + c[i-1]-'0';
		}
		a = b = 0;
		//best = 0.0;
		res1 = 0; res2 = L;
		for (rear = L; rear <= n; rear++) {
			while (b-a>1 && aotu(front[b-2],rear-L,front[b-1],rear-L)<=0)
				b--;//删除凸点，或直线中间一点
			front[b++] = rear - L ;//front队列中加入新点,0起点,rear-front为距离，sum差为序列和
			while (b - a>1 && aotu(front[a],rear, front[a+1],rear)>=0 )
				a++;//front[a]是切点，其后不会再有斜率更小的，因为没有凸点了		
			//从队列前面删除斜率小的，被删除的以后也不会成为最优front;
			//t = (s[rear] - s[front[a]] + 0.0) / (rear-front[a]);
//可能是double的精度有限，找最大斜率t会WA
			i = aotu(res1,res2,front[a],rear);
			if (i > 0 || (i==0 && rear - front[a] < res2 - res1) ) {
				//best = t;
				res1 = front[a];
				res2 = rear;
			}
		}
		printf("%d %d\n", res1+1,res2);//起点+1
	}
	return 0;
}

/*
2
17 5
00101011011011010
20 4
11100111100111110000



7 11
6 9

*/