[BZOJ]5090: 组题 01分数规划

Description

著名出题人小Q的备忘录上共有n道可以出的题目，按照顺序依次编号为1到n，其中第i道题目的难度系数被小Q估计为a_i，难度系数越高，题目越难，负数表示这道题目非常简单。小Q现在要出一套难题，他决定从备忘录中选取编

号连续的若干道题目，使得平均难度系数最高。当然，小Q不能做得太过分，一套题目必须至少包含k道题目，因此他不能通过直接选取难度系数最高的那道题目来组成一套题。请写一个程序，帮助小Q挑选平均难度系数最高的题

目。

题解:

感觉题解的做法好复杂啊……看到平均数就想分数规划，那么将问题转化为判定性问题。设 s[i] 为 a[i] 的前缀和，当前二分的答案为 mid ，那么我们的目标就是找到：

s[j]−s[i−1]j−(i−1)>=mid

移项得： s[j]−j×mid−(s[i−1]−(i−1)×mid)>=0

那么只要每次求出前缀和，然后再减去下标乘 mid ，找有没有 j−i+1>=k 且 s[j]−s[i−1]>=0 就可以了。那么怎么找呢？这个也十分简单，设 mn[i] 为 0 到i位置的 s[i] 最小值，那么对于每个 s[i] ，找 s[mn[i−k]] 就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const long double eps=;
const int Maxn=;
const int inf=;
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<)+(x<<)+(ch^),ch=getchar();
    return x*f;
}
LL gcd(LL a,LL b){return((!b)?a:gcd(b,a%b));}
LL x,y,sum[Maxn];
int n,k,q[Maxn],mn[Maxn];
long double a[Maxn],s[Maxn],t;
bool check(long double v)
{
    s[]=mn[]=;
    for(int i=;i<=n;i++)s[i]=s[i-]+a[i];
    for(int i=;i<=n;i++)s[i]-=v*(long double)(i);
    for(int i=;i<=n;i++)
    {
        if(s[i]<s[mn[i-]])mn[i]=i;
        else mn[i]=mn[i-];
    }
    for(int i=k;i<=n;i++)
    if(s[i]>=s[mn[i-k]]){y=i;x=mn[i-k];return true;}
    return false;
}
int main()
{
    n=read(),k=read();sum[]=;
    for(int i=;i<=n;i++)scanf("%Lf",&a[i]),sum[i]=sum[i-]+(LL)(a[i]);
    long double l=-,r=;
    while(l+eps<=r)
    {
        long double mid=(l+r)/;
        if(check(mid))l=mid;
        else r=mid;
    }
    l=(l+r)/;int u=;
    if(l<)l=-l,u=;
    LL t1,t2;
    t1=(LL)(l*(long double)(y-x)+);t2=y-x;
    LL g=gcd(abs(t1),t2);
    if(u)printf("-");printf("%lld/%lld",t1/g,t2/g);
}