Description

蛋蛋非常热衷于挑战自我, 今年暑假他准备沿川藏线骑着自行车从成都前往拉萨. 川藏线的 沿途有着非常美丽的风景, 但在这一路上也有着很多的艰难险阻, 路况变化多端, 而蛋蛋的 体力十分有限, 因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情.

由于蛋蛋装备了一辆非常好的自行车, 因此在骑行过程中可以认为他仅在克服风阻做功 (不受 自行车本身摩擦力以及自行车与地面的摩擦力影响). 某一天他打算骑 \(n\) 段路, 每一段内 的路况可视为相同: 对于第 \(i\) 段路, 我们给出有关这段路况的 \(3\) 个参数 \(s_i, k_i, \mathop{{v_i}'}\), 其中 \(s_i\) 表示这段路的长度,\(k_i\) 表示这段路的风阻系数,\(\mathop{{v_i}'}\) 表示这段路上的风速 (表示在这段路上他遇到了顺风, 反之则意味着他将受逆风影响). 若某一时刻在这段 路上骑车速度为 \(v\), 则他受到的风阻大小为 \(F = k_i \cdot (v - \mathop{{v_i}'})^2\) (这样若在长度为 \(s\) 的路程内保持骑行速度 \(v\) 不变, 则他消耗能量 (做功 \(E = k_i \cdot (v - \mathop{{v_i}'})^2 \cdot s\)) .

设蛋蛋在这天开始时的体能值是 \(Eu\), 请帮助他设计一种行车方案, 使他在有限的体力内用最短的时间到达目的地. 请告诉他最短的时间 \(T\) 是多少.

提示: 必然存在一种最优的体力方案满足: 蛋蛋在每段路上都采用匀速骑行的方式.

Input

第一行包含一个正整数 \(n\) 和一个实数 \(Eu\), 分别表示路段的数量以及蛋蛋的体能值.

接下来 \(n\) 行分别描述 \(n\) 个路段, 每行有 \(3\) 个实数 \(s_i, k_i, \mathop{{v_i}'}\), 分别表示第 \(i\) 段路的长度, 风阻系数以及风速.

Output

输出一个实数 \(T\), 表示蛋蛋到达目的地消耗的最短时间, 要求至少保留到小数点后 \(6\) 位.

本题没有部分分, 你程序的输出只有和标准答案的差距不超过 \(0.000001\) 时, 才能获得该测试点的满分, 否则不得分.

Sample Input

3 10000
10000 10 5
20000 15 8
50000 5 6

Sample Output

12531.34496464

Data Range

对于 10% 的数据,\(n = 1\);

对于 40% 的数据,\(n \leq 2\);

对于 60% 的数据,\(n \leq 100\);

对于 80% 的数据,\(n \leq 1000\);

对于所有数据,\(n \leq 10000, 0 \leq Eu \leq 10^8, 0 \lt s_i \leq 100000, 0 \lt k_i \leq 1, -100 \lt \mathop{{v_i}'} \lt 100\). 数据保证最终的答案不会超过 \(10^5\).

Explanation

对于 n=1 可以直接求, 考场上可以骗到 10 分......

对于 n=2 可以求解一个二元二次方程, 然后在考场用二分搜索一类的玩意儿来骗分, 大概可以骗到 40 分......

以上就是我什么也不学的能力允许的范围, 以下是 PoPoQQQ 大爷题解, 保证满分:

原文链接:http://blog.csdn.net/popoqqq/article/details/42366599

首先要在 \(\sum_{i=1}^{n} k_i s_i (v_i - \mathop{{v_i}'})^2 \leq E\) 的情况下求出 \(\sum_{i=1}^{n} \frac{s_i}{v_i}\) 的最大值

那么由贪心思想可知要保证 \(\sum_{i=1}^{n} k_i s_i (v_i - \mathop{{v_i}'})^2 = E\) 才能找到最优解

随后套用拉格朗日乘数法, 得到方程组:

\[\begin{cases} -\frac{s_i}{v_i^2} + 2 \lambda k_i s_i (v_i - \mathop{{v_i}'}) = 0 \end{cases}\]

化简得:

\[\begin{cases} 2 \lambda k_i v_i^2 (v_i - \mathop{{v_i}'}) = 1 \end{cases}\]

我们会发现 \(v_i\) 关于 \(\lambda\) 单调递减

由于总能量消耗关于 \(v_i\) 单调递增, 故总能耗关于 \(\lambda\) 单调递减, 我们可以二分 \(\lambda\) 的值

对于每一个 \(\lambda\), 我们需要代入 \(n\) 个方程求出 \(v_i\) 以计算总能耗

由于 \(v_i^2 (v_i - \mathop{{v_i}'})^2\) 关于 \(v_i\) 单调递增, 因此我们可以二分出这个方程的解

无需牛顿迭代, 无需套用求根公式--

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define sqr(__x) ((__x)*(__x))
using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 10010;
const llf epsilon = 1e-12;
const llf infinit = 1e10;

int n;
llf Eu, // The maximum energy that the person is allowed to cost
    s[maxn], // Distance in each interval
    k[maxn], // Air resistance ratio
    v[maxn], // Anticipated velocity of the wind, opposing the person
    x[maxn]; // Final evaluated velocity of the riding speed

llf lagrange(llf lambda)
{
    llf res = 0.0;
    for (int i = 1; i <= n; i++) {
        llf l = max(0.0, v[i]), r = infinit;
        while (r - l > epsilon) {
            llf mid = (l + r) / 2;
            if (2 * lambda * k[i] * sqr(mid) * (mid-v[i]) > 1.0)
                r = mid;
            else
                l = mid;
        }
        x[i] = (l + r) / 2;
        res += k[i] * sqr(x[i] - v[i]) * s[i];
    }
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d%lf", &n, &Eu);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf%lf", &s[i], &k[i], &v[i]);
    // Binary search the area.
    llf l = 0, r = infinit;
    while (r - l > epsilon) {
        llf mid = (l + r) / 2;
        if (lagrange(mid) >= Eu)
            l = mid;
        else
            r = mid;
    }
    // Finalizing to calculate the time
    llf res = 0.0;
    for (int i = 1; i <= n; i++)
        res += s[i] / x[i];
    printf("%.10lf\n", res);
    return 0;
}