首页 > 代码库 > POJ - 3658 Artificial Lake
POJ - 3658 Artificial Lake
题意：向N个连续且高度不同的平台灌水，平台各有宽度，且高度各不相同。一开始，先向高度最低的平台灌水，直到灌满溢出，流向其他的平台，直至所有平台都被覆盖。已知每分钟注入高度为1且宽度为1的水，问每个平台恰好被高度为1的水覆盖的时间。
分析：
1、对于每个平台，L代表其左边的平台标号，R代表其右边的平台标号，随着平台被淹没，R，L会随之改变。
2、平台标号为1~n，其两侧平台0和n-1高度初始化为正无穷作为界线，因此只需统计淹没了n个平台的情况即可。
3、Find_lowest();---得到最低的平台标号。
4、update_lowest(cur);---淹没当前平台后，cur更新为水流溢出后，即将流向的平台标号。
5、将当前平台的水注满到与两侧较矮平台齐平的高度，将较矮的平台宽度更新为加上当前平台后的宽度，与此同时，更新当前平台两侧的平台的左右平台标号。
#pragma comment(linker, "/STACK:102400000, 102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 1e5 + 10;const int MAXT = 10000 + 10;using namespace std;int N;struct Node{ int L, R; LL w, h, ans; void read(){ scanf("%lld%lld", &w, &h); }}num[MAXN];int Find_lowest(){ LL mi = LL_INF, cur = 0; for(int i = 1; i <= N; ++i){ if(num[i].h < mi){ mi = num[i].h; cur = i; } } return cur;}int update_lowest(int cur){ while(1){ int l = num[cur].L, r = num[cur].R; if(num[l].h < num[cur].h) cur = l; else if(num[r].h < num[cur].h) cur = r; else return cur; }}void solve(int cur){ int cnt = 0; LL sum = 0; while(cnt < N){ sum += num[cur].w;//将水注满到刚好覆盖该平台 num[cur].ans = sum; ++cnt; int l = num[cur].L, r = num[cur].R; sum += (Min(num[l].h, num[r].h) - num[cur].h - 1) * num[cur].w;//将当前平台的水注满到与两侧较矮平台齐平的高度 num[l].R = r;//更新两侧平台的左右平台 num[r].L = l; if(num[l].h < num[r].h){ num[l].w += num[cur].w; cur = l; } else{ num[r].w += num[cur].w; cur = r; } cur = update_lowest(cur); }}int main(){ scanf("%d", &N); for(int i = 1; i <= N; ++i){ num[i].read(); } for(int i = 0; i <= N + 1; ++i){ num[i].L = i - 1; num[i].R = i + 1; } num[0].w = num[N + 1].w = 1; num[0].h = num[N + 1].h = LL_INF; int cur = Find_lowest(); solve(cur); for(int i = 1; i <= N; ++i){ printf("%lld\n", num[i].ans); } return 0;}
POJ - 3658 Artificial Lake
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。