【NOIP2013中秋节模拟】表白(love)

Description

鸡腿是CZYZ的著名DS，但是不想追妹子的DS不是好GFS，所以鸡腿想通过表白来达到他追到妹子的目的！虽然你对鸡腿很无语，但是故事的设定是你帮助鸡腿找到了妹子，所以现在你必须帮助鸡腿安排表白来实现故事的结局 ！

鸡腿想到了一个很高（sha）明（bi）的做法，那就是去找人来组成表白队伍来增强气势 ！鸡腿有很多好基友来帮忙，鸡腿数了数一共有N个人。但是鸡腿觉得大家排成两队来比较好看，而且鸡腿经过计算，第一队N1个人，第二队N2个人是最佳的队伍。问题来了…有些好基友们虽然很好心但是可能造成不好的影响（形象猥琐），所以鸡腿就给每个人打了分。Q1i表示第i个好基友排到第一队里时的好影响，C1i表示第i个好基友排到第一队里时的不良影响，Q2i表示第i个好基友排到第二队里时的好影响，C2i表示第i个好基友排到第二队里时的不良影响。请给鸡腿一种安排使得Q的和与C的和的比值最大，给出最大值。

Input

第一行给出三个整数N、N1、N2。

第2到N+1行，每行四个整数Q1,C1,Q2,C2。

Output

一行输出一个小数d表示最优化比例是d（保留6位小数）

Sample Input

5 2 2

12 5 8 3

9 4 9 4

7 3 16 6

11 5 7 5

18 10 6 3

Sample Output

2.444444

Data Constraint

对于50%的数据0 < N1 + N2 ≤ N ≤ 50；

对于100%的数据0 < N1 + N2 ≤ N ≤ 500，1 ≤ Q1, Q2 ≤ 2000，1 ≤ C1, C2 ≤ 50。

solution

首先对于一个答案是否合法，我们可以可以可以看

∑x∈firstgroup(q1i−c1i∗k)∑x∈secondgroup(q2i−c2i∗k)≥0 ∑ x ∈ f i r s t g r o u p ( q 1 i − c 1 i ∗ k ) ∑ x ∈ s e c o n d g r o u p ( q 2 i − c 2 i ∗ k ) ≥ 0

那么我们可以二分一个答案mid，

然后我们按 (q1i−c1i∗k)−(q2i−c2i∗k) ( q 1 i − c 1 i ∗ k ) − ( q 2 i − c 2 i ∗ k ) 的降序排序，用f[i][j] 表示前i 个人取了j 个进第一队，用g[i][j] 表示后i 个人取了j 个进第二队，最后用f[i][N1] +g[N-i][N2]来更新答案即可。

code

uses
        math;
const
        eps=e-;
var
        i,j,k,n,m,n1,n2:longint;
        q1,c1,q2,c2:array[..] of longint;
        a,b:array[..] of extended;
        f,g:array[..,..] of extended;
        l,r,mid:extended;
procedure qsort(x,y:longint);
var
        i,j:longint;
        mid:extended;
begin
        i:=x;
        j:=y;
        mid:=a[(x+y) div ]-b[(x+y) div ];
        repeat
                while a[i]-b[i]>mid do inc(i);
                while a[j]-b[j]<mid do dec(j);
                if i<=j then
                begin
                        a[]:=a[i];a[i]:=a[j];a[j]:=a[];
                        b[]:=b[i];b[i]:=b[j];b[j]:=b[];
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if i<y then qsort(i,y);
        if x<j then qsort(x,j);
end;
function pd(x:extended):boolean;
var
        i,j:longint;
begin
        for i:= to n do
        begin
                a[i]:=q1[i]-x*c1[i];
                b[i]:=q2[i]-x*c2[i];
        end;
        qsort(,n);
        fillchar(f,sizeof(f),);
        fillchar(g,sizeof(g),);
        for i:= to n do
        begin
                for j:= to min(i,n1) do
                begin
                        f[i,j]:=f[i-,j-]+a[i];
                        if i->=j then
                                f[i,j]:=max(f[i,j],f[i-,j]);
                end;
        end;
        for i:=n downto  do
        begin
                for j:= to min(n2,n-i+) do
                begin
                        g[n-i+,j]:=g[n-i,j-]+b[i];
                        if n-i>=j then
                                g[n-i+,j]:=max(g[n-i+,j],g[n-i,j]);
                end;
        end;
        for i:=n1 to n-n2 do
                if f[i,n1]+g[n-i,n2]>= then exit(true);
        exit(false);
end;
begin
        assign(input,'love.in');
        reset(input);
        assign(output,'love.out');
        rewrite(output);
        readln(n,n1,n2);
        for i:= to n do
                readln(q1[i],c1[i],q2[i],c2[i]);
        l:=;
        r:=;
        while (l+eps<r) do
        begin
                mid:=(l+r)/;
                if pd(mid) then l:=mid
                else r:=mid;
        end;
        //writeln(pd(150.050505));
        writeln(l::);
        close(input);
        close(output);
end.