列表

详情

NC24952. [USACO 2008 Jan G]Artificial Lake

描述

The oppressively hot summer days have raised the cows' clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 <= N <= 100,000) conveniently numbered 1..N from left to right. Each level i is described by two integers, its width W_i (1 <= W_i <= 1,000) and height (like a relative elevation) H_i (1 <= H_i <= 1,000,000). The heights of FJ's levels are unique. An infinitely tall barrier encloses the lake's model on the left and right. One example lake profile is shown below.          *             *  :          *             *  :          *             *  8          *    ***      *  7          *    ***      *  6          *    ***      *  5          *    **********  4 <- height          *    **********  3          ***************  2          ***************  1 Level    |  1 |2|  3   |  In FJ's model, he starts filling his lake at sunrise by flowing water into the bottom of the lowest elevation at a rate of 1 square unit of water per minute. The water falls directly downward until it hits something, and then it flows and spreads as room-temperature water always does.  As in all good models, assume that falling and flowing happen instantly. Determine the time at which each elevation's becomes submerged by a single unit of water.      WATER              WATER OVERFLOWS                             |                       |                                 * |          *      *     |      *      *            *      * V          *      *     V      *      *            *      *            *      *    ....    *      *~~~~~~~~~~~~*      *    **      *      *~~~~** :    *      *~~~~**~~~~~~*      *    **      *      *~~~~** :    *      *~~~~**~~~~~~*      *    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*      *    *********      *~~~~*********      *~~~~*********      *~~~~*********      *~~~~*********      *~~~~*********      **************      **************      **************      **************      **************      **************       After 4 mins        After 26 mins       After 50 mins      Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged  Warning: The answer will not always fit in 32 bits.

输入描述

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes level i with two space-separated integers: W_i and H_i

输出描述

* Lines 1..N: Line i contains a single integer that is the number of minutes that since sunrise when level #i is covered by water of height 1.

示例1

输入: 

3
4 2
2 7
6 4

输出: 

4
50
26

说明:

Three levels just as in the example above. Water will fill the first level because it is the lowest.
As in the illustrations above.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 204ms, 内存消耗: 5996K, 提交时间: 2019-07-30 17:44:52 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long 
const ll inf=1e12;
int n;
struct node
{
	ll w,h;
	int id;
}p[N],s[N];
ll ans[N];
int main()
{
	cin>>n;
	int mi=INT_MAX,id;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].w>>p[i].h;
		p[i].id=i;
		if(mi>p[i].h)//找到最小的向两侧扩展 
		{
			mi=p[i].h;
			id=i;
		}
 	}
 	int top=0;
 	s[0].h=1e12;
 	s[++top]=p[id];
 	p[0].h=p[n+1].h=1e12;
 	int l=id,r=id,x;
	ll now=0;
	for(int i=1;i<=n;i++)
	{
		ll fz=0;//传递 
		if(p[l-1].h<p[r+1].h) x=--l;
		else x=++r;
		while(top&&p[x].h>s[top].h)
		{	
			s[top].w+=fz; 
			ans[s[top].id]=now+s[top].w; 
			fz=s[top].w;
			now+=s[top].w*(min(p[x].h,s[top-1].h)-s[top].h);
			//cout<<s[top].id<<' '<<fz<<' '<<now<<endl;
			top--;
		}
		p[x].w+=fz;
		s[++top]=p[x];
	} 
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 300ms, 内存消耗: 4124K, 提交时间: 2020-02-26 16:57:27 

#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const int N=1e5+5;
struct cs
{
	int x,y,w,h;
	Ll v;
}a[N];
int n,m,k;
Ll now;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].w>>a[i].h;
		a[i].x=i-1;
		a[i].y=i+1;
		if(!k||a[k].h>a[i].h) k=i;
	}
	a[0].h=a[n+1].h=1e9;
	while(a[k].x!=0||a[k].y!=n+1)
	{
		if(a[k].h>a[a[k].x].h)
		{
			k=a[k].x;
			continue;
		}
		if(a[k].h>a[a[k].y].h)
		{
			k=a[k].y;
			continue;
		}
		int h=min(a[a[k].x].h,a[a[k].y].h)-a[k].h;
		a[k].v=now+a[k].w;
		now=now+1ll*a[k].w*h;
		a[a[k].x].y=a[k].y;
		a[a[k].y].x=a[k].x;
		if(a[a[k].x].h>a[a[k].y].h)
		a[a[k].y].w+=a[k].w,k=a[k].y;
		else a[a[k].x].w+=a[k].w,k=a[k].x; 
	}
	a[k].v=now+a[k].w;
	for(int i=1;i<=n;i++) cout<<a[i].v<<endl;
}

上一题

© 2024 nowcoder.com