【程序设计训练】公交系统

电玩女神 2022-11-27 12:26 139阅读 0赞

> 个人思路仅供参考，如有不足欢迎交流。

## 【问题描述】 ##

城市公交系统有一个记录仪，用于记录每个站点的乘客人数的变化情况，例如：x表示到站前公交车上的乘客人数，y表示离站时公交车上的乘客人数，则该记录仪记录的该站的数字为y-x。

对于一辆公交车和n个车站，a1,a2,…,an为该公交车在各站的记录数据。

假定w为该公交车可容纳的最大乘客人数，编程求出在第一站停靠之前公交车上人数的可能数据有多少种？

## 【输入形式】 ##

第一行包含两个数据n和w(1<=n<=1000, 1<=w<=109)，分别表示车站的数目和公交车可容纳的最大乘客人数。

第二行包含一个序列a1,a2,…,an，表示记录仪记录的各站的数据。

## 【输出形式】 ##

输出一个整数，表示公交车在第一站停靠之前可能的乘客人数数据的个数，如果没有，则输出0。

## 【样例输入1】 ##

3 5
    2 1 -3

## 【样例输出1】 ##

## 【样例输入2】 ##

2 4
    -1 1

## 【样例输出2】 ##

## 【样例输入3】 ##

4 10
    2 4 1 2

## 【样例输出3】 ##

## 【样例说明】 ##

*  在第一个样例中，乘客数可能有0、1、2，共3种情况
 *  在第二个样例中，乘客数可能有1、2、3、4，共4种情况
 *  在第三个样例种，乘客数可能为0或1，共2种情况

## 【提交代码】 ##

（10/10分，C++）

//50.公交系统
    #include <iostream>
    
    using namespace std;
    
    int reco[1000]; //最多1000个车站
    int main()
    {
        
        int n, w;    //车站数目、最大人数
        int num_pos; //可能情况的数量
        cin >> n >> w;
    
        num_pos = w + 1; //从0到w一共w+1种可能
        for (int i = 0; i < n; i++)
        {
        
            cin >> reco[i]; //每一站的人数增减记录
            if (i != 0)
            {
        
                reco[i] = reco[i - 1] + reco[i]; //相对于最开始的人数增减
            }
        }
        for (int i = 0; i <= w; i++) //i可能的初始人数
        {
        
            for (int j = 0; j < n; j++) //reco[j]每一个车站相对于初始人数的增减
            {
        
                if (i + reco[j] > w || i + reco[j] < 0) //超出范围
                {
        
                    num_pos -= 1; //可能情况数量-1
                    break;
                }
            }
        }
        cout << num_pos;
        return 0;
    }