[文章目录]
Description
著名出题人小Q的备忘录上共有n道可以出的题目，按照顺序依次编号为1到n，其中第i道题目的难度系数被小Q估计为a_i，难度系数越高，题目越难，负数表示这道题目非常简单。小Q现在要出一套难题，他决定从备忘录中选取编号连续的若干道题目，使得平均难度系数最高。当然，小Q不能做得太过分，一套题目必须至少包含k道题目，因此他不能通过直接选取难度系数最高的那道题目来组成一套题。请写一个程序，帮助小Q挑选平均难度系数最高的题目。n<=10^5
傻题。分数规划求出区间，再求答案即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,k;
double a[101000];
inline ll Abs(ll x){return x>0?x:-x;}
ll gcd(ll x,ll y) {return !y?x:gcd(y,x%y);}
long double s[101000];
int al=1,ar=1;
bool check(double x)
{
double re=-1.0,mi=1; int l=0,r=0,tmp=0;
for(int i=1;i<=n;++i)
{
s[i]=s[i-1]+a[i]-x;
if(i>=k)
{
if(s[i-k]<mi) mi=s[i-k],tmp=i-k+1;
if(s[i]-mi>re) re=s[i]-mi,r=i,l=tmp;
}
}
if(re>0) al=l,ar=r;
return re>0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i) scanf("%lf",a+i);
double l=-100000000,r=100000000,mid;
int t=64;
while(t--)
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
ll ans1=0,ans2=ar-al+1;
for(int i=al;i<=ar;++i) ans1+=a[i];
ll tmp=gcd(Abs(ans1),ans2);
printf("%lld/%lld\n",ans1/tmp,ans2/tmp);
return 0;
}