Article From:

[POJ2976]Dropping tests



Here you are\(\{a_1,a_2…a_n\}\)and\(\{b_1,b_2…b_n\}\),structure\(\{c_1,c_2…c_k\}\),among\(c_1<c_2<…<c_k\)And\(c_i\in[1,n]\),Maximization\(L=\frac{\sum_{i=1}^{k}a_{c_i}}{\sum_{i=1}^{k} b_{c_i}}\)


Fractional planning.
Two points one answer\(mid\)。order\(d_i=a_i-mid*b_i\),Then check whether it can be selected\(k\)individual\(d_i\)Make it more than the sum of\(0\)。If you meet the requirements, you can get a little bit of the formula.\(mid\)The solution, so the order\(l=mid\)。If not satisfied is the order\(r=mid\)
In fact, there is a better than two point method called\(Dinkelbach\)。The complexity may be better than two points, but the algorithm itself needs to calculate a new answer based on the current answer to keep approaching the final answer, and there are some differences between calculating one answer and judging an answer in the two point.
about\(Dinkelbach\)The algorithm is not introduced here. A blog of Amway poked me.


using namespace std;
int gi()
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
const int N = 1e3+5;
const double eps = 1e-4;
int n,k,a[N],b[N];double d[N];
int main()
    while (233){
        if (n+k==0) break;
        for (int i=1;i<=n;++i) a[i]=gi();
        for (int i=1;i<=n;++i) b[i]=gi();
        double l=0,r=1;
        while (r-l>eps){
            double mid=(l+r)/2,tmp=0;
            for (int i=1;i<=n;++i) d[i]=(double)a[i]-mid*b[i];
            for (int i=n;i>k;--i) tmp+=d[i];
            if (tmp>eps) l=mid;else r=mid;
    return 0;
Link of this Article: [POJ2976]Dropping tests

Leave a Reply

Your email address will not be published. Required fields are marked *