题解

1 条题解

  • 0
    @ 2024-10-12 11:19:24

    处理技巧:把终点看成第N+1个站点,距离为D,油价为0

    无解特判:
    B<a[1].x 或者 某相邻站点之间距离大于G

    贪心:

    从站点1开始,依次考察每个站点的加油量

    对于站点i,向后找到第一个油价小于a[i].p的站点j,此时情况讨论站点i的加油量:

    1、如果a[j].x-a[i].x<=G,则
    若剩余能到大i,则不加油,否则在i加油到刚好到大j即可,直接行使到j,即i=j。
    2、如果a[j].x-a[i].x>G,则需要在i站点加满油,此时应行使到下一站点,即i++

  • 1

信息

ID
2155
难度
9
分类
贪心 点击显示
标签
递交数
3
已通过
1
通过率
33%
被复制
6
上传者