复赛二：公路(road)
洛谷：P9749
OJ:P4979
【题目描述】
小苞准备开着车沿着公路自驾。
公路上一共有 n 个站点，编号为从 1 到n。其中站点 i 与站点i+1 的距离为vi 公里。
公路上每个站点都可以加油，编号为i的站点一升油的价格为ai 元，且每个站点只出售整数升的油。
小苞想从站点 1 开车到站点 n，一开始小苞在站点 1 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进d 公里。问小苞从站点 1 开到站点 n，至少要花多少钱加油？
【输入】
输入的第一行包含两个正整数 n 和d，分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含n−1 个正整数v1,v2…vn−1 ，分别表示站点间的距离。
输入的第三行包含 n 个正整数 a1,a2…𝑎𝑛 ，分别表示在不同站点加油的价格。
【输出】
输出一行，仅包含一个正整数，表示从站点 1开到站点 n，小苞至少要花多少钱加油。
【输入样例】
5 4
10 10 10 10
9 8 9 6 5
【输出样例】
79
【提示】
【样例 1 解释】
最优方案下：小苞在站点 1 买了 3 升油，在站点2 购买了 5 升油，在站点 4 购买了 2 升油。
【数据范围】
对于所有测试数据保证：1≤n≤105 ，1≤d≤105 ，1≤vi≤105 ，1≤ai≤105 。
| 测试点 | n≤ | 特殊性质 |
| 1∼5 | 8 | 无 |
| 6∼10 | 103 | 无 |
| 11∼13 | 105 | A |
| 14∼16 | 105 | B |
| 17∼20 | 105 | 无 |
特殊性质 A：站点 1 的油价最低。
特殊性质 B：对于所有1≤i<n，vi为 d的倍数。
代码实现：洛谷85分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | /**************************************************************** * Description: CSP_J_R_2 road * Author: Alex Li * Date: 2024-07-01 16:23:08 * LastEditTime: 2024-07-02 10:10:04 ****************************************************************/ #include <iostream> #include <vector> #include <cmath> using namespace std; int main(){ int a,b,n,d,e,sum=0,c=0; bool f; cin>>a>>b; vector<int> sn(a+1,0); vector<int> co(a+1,0); for(int i=0;i<a-1;i++){ cin>>n; sn[i]=n; } for(int i=0;i<a;i++){ cin>>n; co[i]=n; } for(int i=0;i<a-1;i++){ d=sn[i]-c; e=i; f=true; while(f){ if(co[i]<co[e+1]){ d+=sn[e+1]; if((e+1)==(a-1)){ sum+=ceil(d/(b*1.0))*co[i]; cout<<sum; return 0; } e++; }else{ sum+=ceil(d/(b*1.0))*co[i]; if(d%b!=0)c=b-d%b; else c=0; f=false; i=e; } } } cout<<sum; } |
满分代码：
贪心策略： 每次行驶到一个站点，记录所需油量，并且在有更便宜的油价时更新最低油价，始终按照最低油价加油以减少花费。
向上取整：(s + d - 1) / d 是一种常用的向上取整技巧，用来计算加油的升数，确保可以顺利到达下一个站点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <iostream> #include <climits> using namespace std; using LL = long long; const int N = 1e5 + 10; // 最大站点数 int v[N], a[N]; // v[] 保存站点之间的距离，a[] 保存各站点油价 int n, d; // n 表示站点数，d 表示每升油可以行驶的距离 int main() { // 输入站点数 n 和 每升油行驶的距离 d cin >> n >> d; // 输入站点之间的距离 for (int i = 1; i < n; i++) { cin >> v[i]; } int mi = INT_MAX; // 记录当前的最低油价 LL ans = 0, s = 0; // ans 记录总花费，s 记录需要加的油量 // 输入每个站点的油价，并计算最低费用 for (int i = 1; i < n; i++) { cin >> a[i]; // 输入第 i 个站点的油价 s += v[i]; // 需要加的油量为从当前站点到下一个站点的距离 // 更新最低油价 mi = min(mi, a[i]); // 如果还需要加油 if (s > 0) { // 计算需要加的油量，并乘以当前最低油价 ans += (s + d - 1) / d * mi; // 向上取整计算油量 // 更新剩余未使用的油量 s -= (s + d - 1) / d * d; } } // 输出最小的油费 cout << ans << endl; return 0; } |