P2179 [NOI2012]骑行川藏

NOI2012D2T2

在满足 $\sum_{i=1}^ns_i k_i(x_i-v_i)^2\le E_u$ 的条件下最小化 $\sum_{i=1}^n\frac{s_i}{x_i}$

这个题D2T2没毛病的,我考场能拿40就万幸

考虑n=1的情况,那么我们一定要在这个路段上用光我们的能量才能最快解决,那么只需解个方程

n=2的情况?我们考虑盲猜E函数有单调性,然后二分一下左边用多少能量右边用多少能量

然而他没有,所以我们可以把值域划分为很多段,在每一段中二分~~总有一个答案在而且单调的~~,提高复杂度和正确率

考虑正解,拉格朗日乘子法,我是根本不会的

于是感性一下:

我们每一个路段都有一个类似于性价比的东西,也就是说我们付出的能量越多,这个路段的时间越少,这个性价比是关于E和t的函数

而且这是个数学题啊...我们看到

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

那么是不是感性一下我们每段路匀速,全局是不是最后可以全局每段路调节到同一个性价比最优呢?

这个感性上是贪心证明,因为性价比高的路段你愿意多花能量,但能量花多了会使性价比下降,而我们每次都是选性价比最高的来花能量...所以最后会导致性价比都一样达到最优解

这个过程显然不能模拟

理性理解,我们把样例带进去手算就行了2333

我们对于每个路段画出一个 $t-E$ (需要时间和花费能量)图像,那么性价比好像就是 $t/E$ 啊...这不就是这个路段花费e能量后对应那一点在图像上的导数吗?

那么最优解满足每个路段选取的那一点导数一样,注意这个导数是负的

再来感性理解,这个导数越大(也就是性价比越低),需要能量越多,总时间越少

盲猜这个单调,所以我们可以二分这个公共导数值

最后细节要推一下式子

E=k(v-v')^2

t=\frac{s}{v}

\frac{dt}{dE}=\frac{dt}{dv}/\frac{dE}{dv}=-\frac{s}{v^2}*(2k*(v-v'))=-\frac{s}{2kv^2(v-v')}=x

我们二分这个x就可以算出每一段v进而有E

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
const int MAXN = 1e5 + 7, inf = 0x3f3f3f3f;
#define ll long long
int n;
double E, s[MAXN], k[MAXN], u[MAXN];
double getv(double x, int i)
{
    double l = max(u[i], double(0)), r = 1e5 + 5, mid;
    int cnt = 60;
    while(cnt-- > 0)
    {
        mid = (l + r) / 2;
        if(2 * k[i]*x * mid * mid * (mid - u[i]) > -s[i])l = mid;
        else r = mid;
    }
    //知道这里为什么选择二分求解而不是直接解那个假三次方程吗?
    //因为作者无聊啊
    return (l + r) / 2;
}
double calc(double x)
{
    double sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        double v = getv(x, i);
        //带入x性价比算出这个最优的v
        sum += k[i] * (v - u[i]) * (v - u[i]);
        //计算动量
    }
    return sum;
}

int main()
{
    scanf("%d%lf", &n, &E);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lf%lf%lf", &s[i], &k[i], &u[i]), k[i] *= s[i];
    }
    double l = -inf, r = 0, mid;
    int cnt = 100;
    while(cnt--)
    {
        mid = (l + r) / 2;
        if(calc(mid) <= E)l = mid;//最外层二分导数,注意是负的
        else r = mid;
    }
    mid = (l + r) / 2;
    double ans = 0;
    for(int i = 1; i <= n; ++i)ans += s[i] / getv(mid, i);
    printf("%.10lf\n", ans);
    return 0;
}

吐槽T3三重镇AC0,看来只要提答还在我就过不了NOID2T3....

夏晓光(loveJY)的博客

P2081 [NOI2012]迷失游乐园