P1011 [NOIP 1998 提高组] 车站——探索车站人数规律
在编程世界里，解决实际生活场景的复杂问题是一种极具魅力的挑战。今天，让我们一同深入探讨经典的“车站问题”，并用 C++ 实现一个精妙的解决方案。
题目解析
题目描述了一个火车站点的上、下车人数变化规律。始发站（第 1 站）上车人数为 ( n )，从第 3 站开始，上车人数遵循特定规律：上车人数是前两站上车人数之和，而下车人数等于上一站的上车人数。终点站（第 ( m ) 站）的前一站（第 ( m-1 ) 站）下车人数为 ( k )。我们的任务是找出第 ( s ) 站开出时车上的人数。
输入为四个整数：始发站上车人数 ( n )，车站总数 ( m )，终点站前一站下车人数 ( k )，以及所求站点编号 ( s )。
输出是第 ( s ) 站开出时车上的人数。
解题思路
1. 分析规律，建立数学模型
要解决这一问题，首先需要理解车站人数变化的规律：
- 第 1 站（始发站）：上车人数为 ( n )，下车人数为 0，因此车上人数为 ( n )。
- 第 2 站：上车人数等于第 1 站上车人数（即 ( n )），下车人数也等于第 1 站上车人数（即 ( n )），所以车上人数保持为 ( n )。
- 第 3 站及以后：
- 上车人数为前两站上车人数之和。
- 下车人数等于上一站的上车人数。
可以用数组 ( a[i] ) 表示第 ( i ) 站的上车人数，数组 ( b[i] ) 表示第 ( i ) 站的下车人数。初始条件：
- ( a[1] = n )
- ( a[2] = n )
- ( b[1] = 0 )
- ( b[2] = n )
从第 3 站开始：
- ( a[i] = a[i-1] + a[i-2] )
- ( b[i] = a[i-1] )
车上人数可表示为：
- 第 ( i ) 站开出时车上人数 = 前一站开出时车上人数 + 本站在车上的人数变化（即 ( a[i] - b[i] )）
2. 动态规划求解
基于上述规律，我们可以采用动态规划的方法进行模拟。具体步骤如下：
- 初始化前两站的上车和下车人数。
- 按照规律计算后续各站的上车和下车人数。
- 累积计算每站开出时的车上人数。
3. 特殊条件处理
题目中给出了终点站前一站（第 ( m-1 ) 站）的下车人数为 ( k )。这意味着在计算过程中需要确保第 ( m-1 ) 站的下车人数满足这个条件。如果不符合，需要调整初始参数重新计算。
代码实现
以下是基于上述思路的 C++ 代码实现：
#include <iostream>
using namespace std;
int main() {
int n, m, k, s;
cin >> n >> m >> k >> s;
// 如果只有两个车站，直接输出结果
if (m == 1) {
cout << n << endl;
return 0;
}
// 初始化数组，用于存储每站的上车人数和下车人数
int a[m + 1], b[m + 1];
a[1] = n;
a[2] = n;
b[1] = 0;
b[2] = n;
// 计算每站的上车和下车人数
for (int i = 3; i <= m; i++) {
a[i] = a[i - 1] + a[i - 2];
b[i] = a[i - 1];
}
// 检查终点站前一站的下车人数是否符合条件
if (b[m - 1] != k) {
cout << "No solution" << endl;
return 0;
}
// 计算每站开出时的车上人数
int current = n; // 第1站开出时车上人数
if (s == 1) {
cout << current << endl;
return 0;
}
for (int i = 2; i <= s; i++) {
current += a[i] - b[i];
}
cout << current << endl;
return 0;
}
代码解析
- 输入读取和特殊情况处理：首先读取输入参数，如果车站数 ( m ) 为 1，直接输出始发站人数 ( n )。
- 数组初始化：创建数组 ( a ) 和 ( b )，分别存储每站的上车人数和下车人数，并初始化前两站的值。
- 动态规划计算：从第 3 站开始，根据规律计算各站的上车和下车人数。
- 条件验证：检查终点站前一站的下车人数是否为 ( k )，若不满足则输出无解。
- 车上人数计算：从始发站开始，累加上下车人数变化，计算第 ( s ) 站开出时的车上人数。
总结
通过以上分析和实现，我们成功解决了“车站问题”。这一过程不仅锻炼了我们对动态规划的理解和应用能力，也让我们体会到数学规律在实际问题中的巧妙运用。希望这篇博客能为你带来启发，也期待你在编程的道路上不断探索，发现更多精彩！