火车

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

线性王国只有一条铁路，它有n个车站，按照火车前进的方向编号1到n。在第i个车站会有Ai个乘客下车，同时会有Bi个乘客上车。火车在到达第一个车站前是空的，同样在到达最后一个车站后，车上所有的乘客都会下车，火车也会变成空的。

你的任务是计算火车的最小容量确保任何时候火车上的总人数都不会超过这个容量。注意，在每个车站，上车的乘客都是在下车乘客都下来之后才开始上的。

输入

多组输入，第一行是一个正整数T，代表组数。

每组输入数据第一行只有一个整数n (2 <= n <= 1000) ——车站的总数。

接下来是n行，每行有两个整数Ai和Bi（0 <= Ai,Bi <= 1000）——分别代表在第i个车站下车和上车的乘客数。车站是沿照火车前进方向从起点到终点按顺序给出的。

注意起点站不会有人下车，终点站不会有人上车。

输出

每组输出只有一个整数代表火车的最小容量（可以是0）。每组输出之后输出一个空行。

示例输入

140 32 54 24 0

示例输出

6

#include <stdio.h>

int main()

{

    int n1,n2,i,j,k,t,m;

    int a[1000][2],ren[1000];

    scanf("%d",&n1);

    for(i=0; i<n1; i++)

    {

        scanf("%d",&n2);

        for(j=0; j<n2; j++)

            for(k=0; k<2; k++)

                scanf("%d",&a[j][k]);

        ren[0]=a[0][1]-a[0][0];

        for(j=1; j<n2; j++)

            ren[j]=ren[j-1]+a[j][1]-a[j][0];

        for(m=0; m<n2-1; m++)

            for(j=0; j<n2-m-1; j++)

                if(ren[j]<ren[j+1])

                {

                    t=ren[j];

                    ren[j]=ren[j+1];

                    ren[j+1]=t;

                }

        printf("%d\n\n",ren[0]);

    }

    return 0;

}