我都不知道为什么会碰到这种奇怪的题..

题目链接:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2592

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=224239

题意:

你是一个勤劳勇敢的园丁= =培养了一堆大嘴花

你面对着n朵花,你可以做一些事情:

1,给所有花都浇水,每浇1个单位的水,第i朵大嘴花会获得w_i点营养值,注意有些大嘴花是从火星引进的所以w_i可能是负数;花费是a

2,给某一朵花施肥,每施1单位的肥,需要花费f_i,这朵花会获得v_i点营养值

如果第i朵花的营养值最终超过th_i,那么在第二天它就会开花并把一个僵尸吃掉,第二天一共会有n个僵尸入侵你的房子,求所有花都开的最小代价

注意肥料和水是按普朗克质量卖所以可以取任意小数

给定n[1,10⁵],m[0,100],w[-100,100],th[-100,100],f[1,100],v[1,100]

多测,求所有花都开的最小代价

所以..

这一题我的做法是..

先按照浇水的临界值O(n log n)的排序(这是瓶颈!)

如果一朵花:(以下f'表示 花费/营养值

th<=0,w>=0,那么这朵花不管你怎么浇水都会开花,不管它

th>0,w=0,直接无视..

th<=0,w<0,那么这朵花的临界值为它开始需要施肥的时候,之后,你每浇水1个单位,你就要多花费w*f'的价格来维持其值到达th

th>0,w>0,那么这朵花的临界值为它开始不需要施肥的时候,之前,你每浇水一个单位,你就可以少花费w*f'的价格

th>0,w<0,这朵花并没有临界值,然而你每浇水1单位,也需要w*f'的价格来维护它

综上,得到如下代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct flower
{
    int w;
    int f_cost;
    int f;
    int th;
    double w_th;
    void read()
    {
        scanf("%d%d%d%d",&w,&f_cost,&f,&th);
        w_th=(double)th/w;
    }
    friend bool operator < (const flower &a,const flower &b)
    {
        return a.w_th<b.w_th;
    }
};
flower a[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        int n,m;
        scanf("%d",&n);
        if (n==0) return 0;
        scanf("%d",&m);
        int i;
        double ans=0;
        for (i=0;i<n;i++)
        {
            a[i].read();
            if ((a[i].w>=0)&&(a[i].th<=0))
            {
                i--;
                n--;
            }
            else if (a[i].w==0)
            {
                ans+=a[i].th*a[i].f_cost/(double)a[i].f;
                i--;
                n--;
            }
        }
        sort(a,a+n);
        double k=0;
        double last_ans=0;
        double last_sol=0;
        for (i=0;i<n;i++)
        {
            if (a[i].th>0)
            {
                last_ans+=a[i].th*a[i].f_cost/(double)a[i].f;
                k-=a[i].w*a[i].f_cost/(double)a[i].f;
            }
        }
        double min_ans=last_ans;
        for (i=0;i<n;i++)
        {
            if (a[i].w_th<0) continue;
            double delta=a[i].w_th-last_sol;
            last_sol=a[i].w_th;
            last_ans+=delta*k;
            last_ans+=delta*m;
            min_ans=min(min_ans,last_ans);
            if (a[i].th>0)
            {
                k+=a[i].w*a[i].f_cost/(double)a[i].f;
            }
            else
            {
                k-=a[i].w*a[i].f_cost/(double)a[i].f;
            }
        }
        printf("%.5lf\n",ans+min_ans);
    }
    return 0;
}