百度C++笔试

时间：2024/07/27（120分钟）
题型：单选10道，多选3道，填空3道，编程2道
编程：
1. 长度为L的路，初始油量P，n个加油站，给出每个加油站位置和加油量，问到终点最少加几次油
dp[i][j] 表示第i个加油站油量为j时最少加几次油，分当前加油站加油和不加油两种方案转移，复杂度O(nL)
下来复盘了一下发现是可以贪心的，先把距离P以内的油站放入优先队列，取出最大的x加上，然后再把P~P+x以内的放入优先队列，以此类推，复杂度O(nlogn)
2. 1到n，有部分数不能选，选出最多的数使得总和不超过m
贪心选最小的能选的数即可