当前位置：首页 > java >正文

每日c/c++题备战蓝桥杯（P1011 [NOIP 1998 提高组] 车站）

java 2025/7/19 8:38:16

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;
}