P9749 [CSP-J 2023] 公路

记录50

#include<bits/stdc++.h> using namespace std; int f(int a,int b){ int t=0; if(a%b) t=1; return a/b+t; } int main(){ int n,d,v[100010]={},a[100010]={},t=0; cin>>n>>d; for(int i=1;i<=n-1;i++) cin>>v[i]; for(int i=1;i<=n-1;i++) cin>>a[i]; int min_=99999; long long sum=0; for(int i=1;i<=n-1;i++){ t+=v[i]; min_=min(min_,a[i]); if(t>0){ //不用担心负数，负数是下一次提前走的 sum+=f(t,d)*min_; t-=f(t,d)*d; } } cout<<sum; return 0; }

题目传送门https://www.luogu.com.cn/problem/P9749

突破点

输入格式

输入的第一行包含两个正整数 n 和 d，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 n−1 个正整数 v1​,v2​…vn−1​，分别表示站点间的距离。

输入的第三行包含 n 个正整数 a1​,a2​…an​，分别表示在不同站点加油的价格。

输出格式

输出一行，仅包含一个正整数，表示从站点 1 开到站点 n，小苞至少要花多少钱加油。

思路

模拟＋贪心，因为需要花最少的钱，所以每一次都要加油到一个价钱更低的地方加油

1. 存储路段跟油价信息👉数组
2. 只要是没遇到比当前价格低的，继续使用当前价格
3. 遇到更低的，选择更低的
4. 记录价格
5. 记录里程变化数

代码简析

#include<bits/stdc++.h> using namespace std; int f(int a,int b){ int t=0; if(a%b) t=1; return a/b+t; } int main(){ int n,d,v[100010]={},a[100010]={},t=0; cin>>n>>d; for(int i=1;i<=n-1;i++) cin>>v[i]; for(int i=1;i<=n-1;i++) cin>>a[i]; int min_=99999; long long sum=0; ... ... return 0; }

int f(int a,int b){}👉向上取整，目的是得到多少升油

存进去对应的数值

int min_=99999;👉存最小加油价格

long long sum=0;👉存总钱数

注意：1≤n≤，1≤d≤，1≤vi​≤，1≤ai​≤。

#include<bits/stdc++.h> using namespace std; int f(int a,int b){ int t=0; if(a%b) t=1; return a/b+t; } int main(){ int n,d,v[100010]={},a[100010]={},t=0; cin>>n>>d; for(int i=1;i<=n-1;i++) cin>>v[i]; for(int i=1;i<=n-1;i++) cin>>a[i]; int min_=99999; long long sum=0; for(int i=1;i<=n-1;i++){ t+=v[i]; min_=min(min_,a[i]); if(t>0){ //不用担心负数，负数是下一次提前走的 sum+=f(t,d)*min_; t-=f(t,d)*d; } } cout<<sum; return 0; }

for(int i=1;i<=n-1;i++){}👉把路段给遍历一遍

t+=v[i];👉t储存路程需要走的路程

min_=min(min_,a[i]);👉比较选最小的价格

if(t>0){}👉只要路程数为正，就是没到终点

sum+=f(t,d)*min_;👉累加当前最小油的价格

t-=f(t,d)*d;👉用当前油可以跑的里程数

补充

CSP-J中INT_MAX及最大最小值定义完全指南

---

1. INT_MAX在CSP-J中的使用（结论：可以，但推荐自己定义）

头文件包含：

#include <bits/stdc++.h> // 万能头已包含<climits>，INT_MAX可用

值是多少：

INT_MAX = 2147483647; // 2^31 - 1，约21.47亿 INT_MIN = -2147483648; // -2^31

CSP-J适用性：

// ✅ 可以使用，但有两个问题： // 1. 增1会溢出：INT_MAX + 1 = INT_MIN = -21亿（负数） // 2. 记忆困难：不如自己定义的1e9直观 // 推荐：手动定义INF const int INF = 1e9; // 十亿，足够大

---

2. CSP-J推荐的最大最小值定义方式（按优先级排序）

方式1：手动定义（最推荐）

// ✅ 推荐度★★★★★ const int INF = 1e9; // 最大正数 const int NEG_INF = -1e9; // 最小负数 const ll LL_INF = 1e18; // long long无穷大（9e18更安全） // 优点： // - 值明确，不会溢出 // - 可读性强 // - 竞赛标配，易于调试

方式2：使用<climits>

#include <climits> // 或 <bits/stdc++.h> // 整数类型极值 INT_MAX // int最大值 (2^31-1) INT_MIN // int最小值 (-2^31) LONG_LONG_MAX // long long最大值 (9.2e18) LLONG_MAX // 同上（C风格） // 示例 int max_val = INT_MAX; // 2147483647 long long max_ll = LLONG_MAX; // 9223372036854775807

方式3：使用<limits>

#include <limits> std::numeric_limits<int>::max(); // 2147483647 std::numeric_limits<int>::min(); // -2147483648 std::numeric_limits<long long>::max(); // 9.2e18 // 缺点：代码冗长，竞赛中没人用

方式4：位运算定义（炫技，可读性差）

const int INF = 0x3f3f3f3f; // 1073741823，约10亿 // 优点：两个INF相加不会溢出int // 缺点：不直观，新手看不懂 const int INF = (1 << 30) - 1; // 1073741823 // 更差，更难记

---

3. CSP-J最大最小值使用场景与推荐

场景	推荐定义	不推荐	原因
DP初始化	const int INF = 1e9;	INT_MAX	1e9足够大，增1不会溢出
long long DP	const ll INF = 1e18;	LLONG_MAX	LLONG_MAX + 1溢出为负
找最小值	int ans = INF;	ans = INT_MAX	INT_MAX + 1错误
乘法初始化	ans = 1e9	ans = INT_MAX	INT_MAX * 2溢出
比较	if (x > INF)	if (x > INT_MAX)	逻辑错误

---

4. 竞赛血泪案例

案例1：INT_MAX + 1溢出

int dp[100]; dp[0] = INT_MAX; for (int i = 1; i < n; i++) { dp[i] = dp[i-1] + 1; // INT_MAX + 1 = -2147483648 } // 结果：dp[1] = -2147483648，后续全部错误

案例2：LLONG_MAX乘法溢出

ll x = LLONG_MAX; ll y = x * 2; // 溢出为负数！ // 正确：判断是否乘法溢出 if (x > INF / 2) y = INF; else y = x * 2;

---

5. CSP-J金牌选手的INF定义模板

#include <bits/stdc++.h> using namespace std; // 类型别名 typedef long long ll; typedef unsigned long long ull; // 无穷大定义 const int INF = 1e9; // int最大值 const int NEG_INF = -1e9; // int最小值 const ll LL_INF = 1e18; // long long最大值（安全） const ll LL_NEG_INF = -1e18; // long long最小值 // 边界判断宏 #define CHECK_OVERFLOW(x) ((x) > INF / 2) ? INF : (x) * 2 // 使用示例 int main() { int dp[N]; fill(dp, dp + N, INF); // 初始化为INF // 比较 int ans = NEG_INF; for (int i = 0; i < n; i++) { ans = max(ans, a[i]); } // long long场景 ll sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; if (sum > LL_INF) sum = LL_INF; // 防溢出 } return 0; }

---

6. 一句话总结

CSP-J中INT_MAX可以用，但推荐用const int INF = 1e9;，因为：①值明确不会溢出 ②增1不会变负 ③可读性强 ④是竞赛标配。
对于long long，用const ll INF = 1e18;替换LLONG_MAX，安全第一。

记忆口诀：INT_MAX是雷区，1e9是平地，LLONG_MAX是悬崖，1e18是护栏。