[正常题解]Acwing.5308 公路

​首先需要理解一个证明：

​ 假设我们有三个点，前两个点价格为\(a_1,\ a_2\)，距离为\(v_1,\ v_2\)

那么就有式子：\(\frac{a_1 \times v_1}{d} + \frac{a_2 \times v_2}{d}\ 式①\)，和式子\(\frac{a_1 \times v_1}{d} + \frac{a_1 \times v_2}{d} \ 式子②\)

$\rightarrow\frac{1}{d} (a_1 \times v_1+ a_2 \times v_2) => 总和 <=\frac{1}{d} (a_1 \times v_1+ a_1 \times v_2) $

假设\(a_1 > a_2\)

\(\therefore a_1 \times v_2 > a_2\times v_2\)

\(\therefore 式①>式②\)

假设\(a_1 < a_2\)

\(\therefore a_1 \times v_2 < a_2 \times v_2\)

\(\therefore 式①<式②\)

​ 从这个推论可以得出：我们实际上是在求一个油价最长下降子序列，并且这个序列必须从1号位开始。

根据以上结论可以先暂时有以下代码：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
int n, d;
int v[N], vs[N], a[N];
queue<int> p;
int main()
{
    scanf("%d%d", &n, &d);
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &v[i]);
        vs[i] = vs[i-1] + v[i];
    }
    int less = 1e9;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        if(less > a[i])
        {
            less = a[i];
            p.push(i);
        }
    }
    long long res = 0;
    int prev = p.front();
    p.pop();
    while(!p.empty())
    {
        int temp = p.front();
        p.pop();
        long long dis = vs[temp] - vs[prev];
        res += dis * a[prev];
        prev = temp;
    }
    cout<<res / d<<endl;
    return 0;
}

​ 但是我们发现距离正确答案差了一点点（样例79，程序77）按照常识来说我们离正确答案挺近的了。问题在哪里呢？

​ 问题在于油是可以买多用不完的，所以我们的d不能在答案的时候才加回来，所以需要在处理过程里买足了再计算剩多少。

​ 但是我要变成Lazy Man了，这个题解就这样发布了吧。