BZOJ-5090: 组题

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注