洛谷p1404 平均数

题目描述

给一个长度为n的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且数列长度>=m。

输入输出格式

输入格式：

N+1行，

第一行两个整数n和m

接下来n行，每行一个整数a[i],表示序列第i个数字

输出格式：

一个整数，他是最大平均数的1000倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

输入输出样例

输入样例#1： 10 6 6 4 2 10 3 8 5 9 4 1 输出样例#1： 6500

说明

【数据范围】

60% M<=N<=10000

100% M<=N<=100000 0<=a[i]<=2000

二分答案 每次判断能不能满足存在长度大于m的子串的平均值>=mid就好 复杂度为O（n log 2000000）

至于怎么判断可以把数列每一项减去mid 如果存在前缀和s[i]< s[j] && j-i>=m那么就满足条件

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=100010; long long n,m,Max; long long a[N],s[N];//为了防止各种越界，全部开longlong int main(){ cin>>n>>m; for (int i=1;i<=n;i++) { cin>>a[i]; a[i]=a[i]*10000;//因为答案要*1000并且舍弃小数 所以可以把原数列的每一项*10000 最后得到的答案/10就好 Max=max(Max,a[i]);//Max为可能的最大平均值 } int l=0,r=Max; while (l<=r) { bool ok=0; long long mid=(l+r)/2,Min=0; for (int i=1;i<=n;i++) { s[i]=s[i-1]+(a[i]-mid); //s[i]为a[i]减掉mid之后的前缀和 if (i>=m) { Min=min(Min,s[i-m]); if (s[i]>Min) { //判断是否平均值能>=mid ok=1; break; } } } if (ok) l=mid+1; else r=mid-1; } cout<<(l/10)<<endl; return 0; }