1 条题解
-
0
何老师 (root) LV 0 MOD @ 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