hust 1218 Acman and his GirlFriend

题目描述

ACman has been studying in HUST for nearly four years, and he thinks Wuhan is a very beautiful city even though he doesn’t like the weird weather. One day, he invited his girl friend Brandy to go shopping, they found that there were many shopping malls in the city center. Brandy had no idea which mall should they enter, because they had only limited time for shopping. She asked ACman for a help. ACman loved Maths as much as Brandy, he considered the beauty in Maths as the most beauty in the world. There were N(1 <= N <= 100000) shopping malls lying on a line, and the distance between the adjacent malls was one meter. Every malls has his own height, and different malls might be the same height. You could select n continuous malls on condition that n must be M(1<=M<=N) at least for some reason, and the beautiful value was defined as the ratio of the sum of the n malls’ heights and the number of the continuous selected malls, namely, n. What was the most beautiful value? As a good programmer, Could you help ACman solve the problem? If you can solve it correctly, ACman will give you a beautiful balloon.

输入

The first line of input is an integer giving number of cases to follow. For each case: The first line contains two integers N, M separated by a single space. The second line contains N integers which represent the heights of the N shopping malls on a line from left to right. The heights of shopping malls are positive integers and less than 100000.

输出

Print a single integer which is the most beautiful value rounded to three digits after the decimal point.

样例输入

1
5 2
1 3 2 7 1

样例输出

4.500
这个题的意思就是求最大的联系数的平均值，而且长度不小于m
这个题一看就用二分法来做，不过怎么判断是否可行呢，
用一个sum表示长度为m的和，k表示紧挨着它，而且值最大的一个系列，当他们两个之和>=平均值时，就是可行的了

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define  inf 0x0f0f0f0f
 
using namespace std;
 
const double pi=acos(-1.0);
const double eps=1e-8;
typedef pair<int,int>pii;
 
const int maxn=100001;
 
double a[maxn],b[maxn];
 
int n,m;
 
bool if_find(double x,int n,int t)
{
    double sum=0.0,k=0;
    for (int i=0;i<n;i++) b[i]=a[i]-x;
    for (int i=0;i<t;i++) sum+=b[i];
    int j=0;
    for (int i=t;i<n;i++)
    {
        if (sum+k>=0) return true;
        sum+=b[i];//sum总是保留t的长度
        sum-=b[i-t];
        k+=b[i-t];//k总是记录sum去掉的数而且k是去掉的和最大的值，以就是k保留的是长度<=t的，紧靠着sum的最大值
        while (k<0 && j<=i-t)
        {
            k-=b[j];
            j++;
        }
    }
    if (sum+k>=0) return true;
    else return false;
}
 
double find(double x,double y)
{
    while (y-x>eps)
    {
        double mid=(y+x)/2.0;
        if (if_find(mid,n,m))x=mid;
        else y=mid;
    }
    return x;
}
 
int main()
{
    //freopen("in.txt","r",stdin);
 
    int t;
    scanf("%d",&t);
    double maxx,minx;
    while (t--)
    {
        maxx=-1.0;
        minx=999999999.0;
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
            maxx=max(maxx,a[i]);
            minx=min(minx,a[i]);
        }
        printf("%.3lf\n",find(minx,maxx));
    }
    //fclose(stdin);
    return 0;
}

hust 1218 Acman and his GirlFriend,布布扣,bubuko.com

hust 1218 Acman and his GirlFriend

原文：http://www.cnblogs.com/chensunrise/p/3683521.html