Codeforces - Tram 列车载人有关问题 题解
Codeforces - Tram 列车载人问题 题解
每站都是先下后上的,那么其实就是个很简单的问题了,可以使用贪心法:
题目:
一列电车,已经知道每站上下车的人数,那么问电车最小需要多大的容量才能让所有乘客都能搭车?
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; }