Tram

╰+攻爆jí腚メ 2022-05-15 04:50 74阅读 0赞

学姐的家离学校很近，所以学姐经常坐公共汽车回家。这天学姐唱着《常回家看看》正等着回家的汽车，突然学姐想起来了一个关于乘车的问题（这证明学姐有敏锐的观察力），然后学姐高高兴兴的回家了，but她没想解决问题的办法。好了，你的问题来了：学姐坐的公共汽车共有n个站点，学姐从第一站开始坐。在她之前车上没有乘客。学姐想的问题是这个车最少需要多少个座位才能保证每个人都能有座位坐。  
Input  
第一行包含单个数字n（2≤n≤1000）表示汽车停靠的次数。  
然后是n行，每行包含两个整数a和b（0≤a，b≤1000）表示在这个站点下车的乘客数量，以及上车的乘客数量。汽车从第一个到最后一个停车点按照电车的运动顺序进行。  
Output  
输出汽车最少需要的座位数。  
Example  
Input  
4  
0 3  
2 5  
4 2  
4 0  
Output  
6  
对于第一个例子，容量为6就足够了：  
在第一站，到达前车内的乘客人数为0.然后，3名乘客进入车，车内的乘客人数为3。  
在第二站，2名乘客离开车（1名乘客留在里面）。然后，5名乘客进入车。现在电车里有6名乘客。  
第三站有4名乘客离开车（内有2名乘客）。然后，2名乘客进入车。现在车里有4名乘客。  
最后，车内的所有剩余乘客在最后一站下车。现在车里没有乘客，这是符合约束的。  
由于电车内的乘客人数从未超过6人，因此6人的容量就足够了。此外，电车的容量不可能小于6.因此，6是正确的答案  
分析：

设容量为ans（初始化为0） 每次下车人数为down 上车人数为up 那么ans=ans+up-down,取最大值

代码总览：

#include <cstdio>
    using namespace std;
    struct node{
        int a,b;
    }p[10000];
    int main()
    {
       int n;
       while(scanf("%d",&n)!=EOF)
       {
        int maxx=0,ans=0;
        for(int i=0;i<n;i++)
        scanf("%d %d",&p[i].a,&p[i].b);
        for(int i=0;i<n;i++)
        {
            maxx+=p[i].b-p[i].a;
            if(maxx>ans)
            {
                ans=maxx;
            }
        }
        printf("%d\n",ans);
       } 
       return 0;    
    }

Tram

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 N - Tram——最短路_spfa()算法

相关 poj-1847-Tram

相关 Tram