首页 / 软件开发 / 数据结构与算法 / Codeforces：Tram 列车载人问题 题解

Codeforces：Tram 列车载人问题 题解2015-02-25题目：

一列电车，已经知道每站上下车的人数，那么问电车最小需要多大的容量才能让所有乘客都能搭车？

Sample test（s）
input

4
0 3
2 5
4 2
4 0

output

6

每站都是先下后上的，那么其实就是个很简单的问题了，可以使用贪心法：

1 初始化第一站乘客为零

2 每站计算上一站有的乘客加上上站的乘客，减去下站的乘客

3 每站剩下乘客的最大量就是结果了

#include <iostream>#include <vector>#include <string> using namespace std; void Tram（）{int a = 0, b = 0, min_contain = 0, left = 0;int T = 0;cin>>T;while （T--）{cin>>a>>b;left = left + b - a;min_contain = max（min_contain, left）;}cout<<min_contain;}int main（）{Tram（）;return 0;}

From：csdn博客 靖心