2023 CSP-J T2 公路题解

lingmori · 2023-10-25 11:28:44 · 个人记录

2023 [CSP-J] T2 公路

PART 1. 前言

考场上没有想到贪心正解......

考场上想的是用一个不上升子序列记录油价的更迭，之后再挨个计算油价 ~~（然后考场上调最后计算油价调炸了只得了大概40pts）~~，总体上，是个伪装成动态规划的贪心的算法（？）

PART 2.正篇

~~因为自己没有打暴力，所以没有暴力的解析，直接上正解分析！~~

第一眼可能会觉得这是一个背包，但实际上分析之后可以发现是一个纯粹的贪心。根据数据点的特殊性质 A：站点 1 的油价最低。

一.在哪里买油？

很容易想到这个性质的解决方法：直接计算需要多少油 * 站点1的油价，因为在其余站点买油一定会更贵。

根据这个能很容易想到如果要保证最低花费，应该尽量在油价低的站点买尽量多的油，我们可以用一个循环模拟这个比较、买油的过程。但注意，比较的应该放在到达之后，因为你必须先到达这个点，在之后的点才能买这里的油。比较并更新的过程放在循环最后。

二.买多少

特殊性质 B：对于所有1<=i<n,vi为d的倍数。根据这个特殊性质，解法是直接用距离除以d就能得到，以此类推，对于其余不保证特殊性质B的点，应该买的是用距离/d向上取整的这么多油。但实际上，我们是一定不会用到这么多油，因为只能买整数的，所以会有剩余。剩余的油也可以用，这个时候特判一下下一个点的与这一个点的距离目前剩下的油能不能支撑，如果能支撑的不用买了即如下代码:（这里用have表示目前的油能够走的路程）

if(v[i]<=have)//能用 
{
   have-=v[i];
}

如果不能满足条件，就需要买油。为了最后答案尽可能小且能够走到下一个点，就买vi/d向上取整这么多就够了，然后减去这一段路程并加上买的油能够支撑的路程，这样可以得出我们的核心代码：

for(int i=1;i<=n;i++)
{
    if(v[i]<=have)//能用 
    {
        have-=v[i];
    }
    else//不够 
    {
        int o=(v[i]-have+d-1)/d;//从这一个点到下一个点需要花费的油 
       ans+=o*last;
        have+=o*d;  
        have-=v[i];//减去路程 
    }
    last=min(last,p[i]);
}

last代表目前最低的油价，o是在这个站需要买的油，ans是最终答案，也就是需要花费的钱。

~~由于数据范围，记得答案开long long不然会爆~~

Code(100pts):

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6;
long long n,d;
long long v[N],p[N];
long long last=0x3f3f3f3f,ans=0,have=0;//目前的最低油价/花的钱/目前的油能走多少公里 
int main()
{
    scanf("%lld%lld",&n,&d);
    v[1]=0;
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(v[i]<=have)//能用 
        {
            have-=v[i];
        }
        else//不够 
        {
            int o=(v[i]-have+d-1)/d;//从这一个点到下一个点需要花费的油 
            ans+=o*last;
            have+=o*d;  
            have-=v[i];//减去路程 
        }
        last=min(last,p[i]);
    }
    printf("%lld",ans);
 }

感谢观看！

2023 CSP-J T2 公路 题解