题目

题目描述

很久以前，cxm做了一个题，叫“抢车位”，大意是让你调度的汽车使得每个汽车都有位。AC以后，cxm去实地考察了这个游戏，发现最有意思的地方是“以旧换新”：你最多拥有$10$辆汽车，便宜的汽车换贵只用补差价
但是贵的汽车不能换便宜，价格相同的汽车也不能互换。每个汽车有一个赚钱速度，即每分钟会从这汽车得到多少的钱
假定汽车在任何时候都要赚钱 (在原游戏中即为始终能找到位置停车)，cxm发现需要设计一个换车的策略，使得自己以最快的速度拥有$M$的资产 (资产包括现金 + 汽车的价值，这个$M$大于等于最贵车价格的$2$倍的)
cxm想了一个算法，于是这次简化版：只考虑有$2$辆汽车的情况，规则与游戏中稍不同，收益是随时发放和均摊的，即如果收益为$7$金每分钟，你可以在$\frac{3}{14}$分钟的时候得到$1.5$金
最开始你的“汽车”为$2$辆价值为$0$，赚钱速度为$1$金每分钟的$11$路汽车

输入格式

第一行两个正整数$N$和$M$，表示有$N$种汽车和最终需要达到的资产
接下来$N$行，每两个正整数$w_i$和$v_i$，表示第 i种汽车的价值为$w_i$金，赚钱速度为$v_i$金每分钟

输出格式

包含一行一个浮点数(不限位数)，表示达到$M$的资产最少需要的时间
只要你的答案与标准答案差别不超过$0.001$我们就认为你的答案是正确的（正式评测时我们用C++的double类型存储你的答案和标准答案并参与判断）

样例

样例输入1

样例输出1

36.4762

样例输入2

样例输出2

21.2418

样例输入3

样例输出3

19.425199

数据范围与提示

样例1解释

第一步：将第一辆换成第一种车
第二步：将第一辆换成第二种车
第三步：将第二辆换成第一种车
第四步：将第二辆换成第二种车
第五步：将第一辆换成第三种车
第六步：等待赚够$85$金的现金(也可以认为将第二辆换成了第三种车然后等待赚够$0$金)
总共耗时$\frac{10}{2}+\frac{5}{3}+\frac{10}{4}+\frac{5}{5}+\frac{85}{6}+\frac{85}{7}\approx 36.4762$

数据范围

有$20\%$的数据$N\leqslant 10$
另有$20\%$的数据$N\leqslant 30$且$M\leqslant 2000$
有$60\%$的数据$N\leqslant 300$
$100\%$的数据$N\leqslant 3000,M<=10^9,2w_i\leqslant M,2\leqslant v_i\leqslant 10^5$

来源

BJWC2015

题解

不得不说，这真是一个沙雕题……~~只有我这个沙雕错了……~~
首先，那些$w_i$增加，$v_i$减少或者不变的汽车都没有用（显然）
假设去掉之后只有$len$种车且从小到大排序好了
最优的方法显然是把两辆车都从$(w_1,v_1)$一直换到$(w_{len},v_{len})$（显然）
所以，我们只需要计算$f_{i,j}$，表示把第一辆车变成第$i$种车，并把第二辆车变成第$j$种车花的钱
由此，我们可以列出递推式：$f_{i,j}=min(f_{i,j-1}+\frac{w_j}{v_i+v_{j-1}},f_{i-1,j}+\frac{w_i}{v_{i-1}+v_j})$
直接暴力计算即可，效率$\Theta(len^2)$
附上代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct ppap
{
    int w,v;
}c[3010],q[3010];
int n,m,len,s;
double f[3010][3010];
int cmp(const ppap &a,const ppap &b)
{
    return (a.w<b.w||(a.w==b.w&&a.v>b.v));
}
int main()
{
    scanf("%d%d",&n,&m),q[0].w=f[0][0]=0,q[0].v=1;
    for(int i=1;i<=n;i++) scanf("%d%d",&c[i].w,&c[i].v);
    sort(c+1,c+n+1,cmp);cout<<endl;
    for(int i=1;i<=n;i++) if(q[len].w<c[i].w&&q[len].v<c[i].v) q[++len]=c[i];
    for(int i=1;i<=len;i++) f[i][0]=f[i-1][0]+1.0*(q[i].w-q[i-1].w)/(q[i-1].v+1);
    for(int i=1;i<=len;i++) f[0][i]=f[0][i-1]+1.0*(q[i].w-q[i-1].w)/(q[i-1].v+1);
    for(int i=1;i<=len;i++) for(int j=1;j<=len;j++)
        f[i][j]=min(f[i-1][j]+1.0*(q[i].w-q[i-1].w)/(q[i-1].v+q[j].v),f[i][j-1]+1.0*(q[j].w-q[j-1].w)/(q[j-1].v+q[i].v));
    printf("%lf",f[len][len]+1.0*(m-q[len].w*2)/(q[len].v*2));
}