P9749 [CSP-J 2023] 公路 题解
wangjue233 · · 个人记录
Solution
题目传送门
题目大意
给你一个 n 和 k ，分别表示公路上站点的数量和车每升油可以前进的距离。然后读入 v_1 ... v_{n-1} 以及 a_1 ... a_n （注意 v_i 表示的是第 i 个站点和第 i + 1 个站点的间距，众所周知间距 = 站点数 - 1 所以小心因为读入问题导致爆 0 ）让你算出小苞至少要花多少元去加油。
题目思路
这道题是一道很明显且较简单的贪心题，贪心出最少需要花的钱，我们可以用 2 个变量来统计路程总和以及油价最小值，然后用 2 个变量来统计上一个站点总共需要的油和这个点需要的油。
画一张对于样例1来说的简略图：
AC Code:
#include<iostream>
#define JZZ long long //用#define把 "JZZ" 定义为 long long，更加方便
using namespace std;
const JZZ inf = 1e11; //const 为不变量，在csp-j2023初赛中也考过const的定义
const int maxn = 1e5 + 10; //好习惯，方便统一数组大小
JZZ a[maxn], v[maxn];
int main(){
int n, d; cin >> n >> d;
for(int i = 1; i <= n - 1; i++) cin >> v[i];
for(int i = 1; i <= n; i++) cin >> a[i];
JZZ mi = inf, u = 0, e = 0;
JZZ sum = 0;
JZZ ans = 0; //不开long long会导致从100pts --> 40pts甚至更低
for(int i = 1; i < n; i++){
mi = min(mi, a[i]); //mi表示油价最小值
sum += v[i];
e = (sum + d - 1) / d; //需要的油
ans += abs((u - e) * mi);
u = e; //u表示上一个点总共需要的油
}
cout << ans << "\n"; //输出最少需要花的钱
return 0;
}