南京理工大学第八届程序设计大赛(校外镜像) J sequence

我不是女神ヾ 2022-08-21 06:50 152阅读 0赞

# water1 #

Time Limit: 1000MS

Memory Limit: 65536KB

## Description ##

听说全球气候变暖，冰川融化，海水淹大地。着实好奇要融化多少冰川会淹没我的宿舍，哦不，淹没南京，反正NJUST应该总会是第一批被淹的。现将问题简化成一个二维坐标系的模型。有N个矩形块区域，每个区域有海拔（H）和宽度（W），区域按照顺序给出，比如有3个区域，第一个区域宽度为1，海拔为2，第二个区域宽度为5，海拔为6，第三个区域宽度为3，海拔为4，从图像上看就是像这样：（Y轴是海拔）8 7 6 +++++5 +++++4 ++++++++3 ++++++++2 +++++++++1 +++++++++ 123456789假设最左边和最右边都是无限高的墙。为了简化问题，假设水流下来的速度是每秒一个单位的水，并且总是往区域一降水（某沿海地区）。现在请问要淹没所有的区域至少要多少时间（秒）？淹没的定义是，所有的区域表面至少覆盖一层水。如果没有区域则至少要放一滴水。上图例子中，淹没完如下：87 wwwwwwwww6 w+++++www5 w+++++www4 w++++++++3 w++++++++2 +++++++++1 +++++++++ 123456789所以需要19秒。

## Input ##

多CASE，测试数据以EOF结尾，对于每个CASE：第一行一个整数N（0 <= N <= 10^5）。接下去N行每行对应两个整数H（1 <= H <= 10^5）,W（1 <= W <= 10^5）分别对应第N个区域的海拔和宽度。

## Output ##

一个整数，表示所需要的时间。

## Sample Input ##

3
    2 1 
    6 5
    4 3

## Sample Output ##

#include <cstdio>
    #define N 100000+10
    int l[N], w[N];
    int main()
    {
    	int t;
    	while(scanf("%d", &t) != EOF)
    	{
    		if(!t)
    		{
    		
    			printf("1\n");
    			continue; 
    		}
    		int maxL= -1;
    			for(int i=0; i< t; i++)
    			{
    				scanf("%d%d", &l[i], &w[i]);
    				if(maxL < l[i])
    					maxL = l[i];
    			}
    			maxL++;
    			long long sum =0;
    			for(int i=0; i< t; i++)
    			{
    				sum += (long long)((maxL-l[i])*w[i]);
    			}
    			printf("%lld\n", sum);
    	}
    	return 0;
    }