这篇文章上次修改于 356 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

分数规划

模板

引入问题

考虑在 $\mathcal O(n \log n \log k)$ 时间复杂度内解决如下问题：

给定一个长度为 $n$ 的序列 $a,b$ 和一个整数 $k$，要求出 $\min{\frac {\sum\limits ^{n} _{i=1} a_i\times s_i} {\sum\limits^{n}_{i=1}b_i\times s_i } }$ 。其中 $s_i \in [0,1]$ 且 $\sum \limits _ {i=1} ^ {n} {s_i} = k$ 。

初步思路

第一眼没有头绪，感觉这一大堆最小值很奇怪，所以先不考虑最小值，只对那个分式作处理。

看了半天没看出什么，经高人指点与直线方程有关，所以就乱搞一下。

令其为 $x$ ，则可变换出 $x\times \sum\limits ^{n} _{i=1} a_i\times s_i -\sum\limits^{n}_{i=1}b_i\times s_i =0$。

是不是非常的直线，写成这样 $y=\sum\limits^{n}_{i=1}b_i\times s_i-\sum\limits ^{n} _{i=1} a_i\times s_i\times x~$。

最终的结果实际上是这样一个方程的 $x$ 截距。

核心内容

然而这样的直线有 $2^n$ 条，所以实际上纯纯小丑。

考虑只维护 $y=-a_i\times x+b_i$ 的直线，然后通过一些处理表达出所有直线。

可以发现实际上原来的直线可以这样表示很有启发性 $y=\sum\limits ^{n} _ {i=1}[s_i\times (-a_i\times x+ b_i)]$。

这代表这什么呢，对，横坐标相同，纵坐标直接加，所以其实判定解合法性很好处理，看看可不可以通过直线的组合使 $y$ 坐标相加为 $0$ 。实际上更快的做法是因为在实数域下本身都是稠密的，而这个具有单调性，所以直接二分看所有的和是否大于 $0$ 即可。

贴上模板题Dropping tests - ZOJ 3068 - Virtual Judge的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
inline int read();
double a[1005];
double b[1005];
int n,k;
double c[1005];
bool check(double mid){
    for(int i=1;i<=n;i++){
        c[i]=a[i]+(-b[i]*mid);
    }
    std::sort(c+1,c+n+1);
    double sum=0;
    for(int i=n;i>=n-k+1;i--){
        sum+=c[i];
    }
    return sum>=0;
}
int main(){
    #ifdef ONLINE_JUDGE
    #else
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    while(scanf("%d%d",&n,&k)!=EOF&&!(n==0&&k==0)){
        double l=0,r=0;
        for(int i=1;i<=n;i++){
            a[i]=read();
            r+=a[i];
        }
        for(int i=1;i<=n;i++){
            b[i]=read();
            r+=b[i];
        }
        k=n-k;
        for(int i=1;i<=100;i++){
            double mid=(l+r)/2;
            if(check(mid)){
                l=mid;
            }else{
                r=mid;
            }
        }
        printf("%d\n",int(l*100+0.5));
    }
    return 0;
}
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        c=='-'?f=-1:1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return f*x;
}

题目分析

[USACO18OPEN] Talent Show G

[USACO18OPEN] Talent Show G - 洛谷

相比模板题多了一个重量限制，注意到选择的 $x$ 与牛无关，单调性仍然成立，中间判定部分可采用 01 背包的做法。

提供二分check的代码：

bool check(long double mid){
  for(int i=1;i<=W;i++){
    dp[i]=-0x3f3f3f3f
  }
  dp[0]=0;
  for(int i=1;i<=n;i++){
    for(int j=W;j>=0;j--){
      dp[std::min(j+w[i],W)]=std::max(dp[std::min(j+w[i],W)],dp[j]+(-w[i]*mid+t[i]));
    }   
  }
  return dp[W]>0;
}