首页 > 代码库 > UVALive 3517:Feel Good（单调栈 Grade C）
UVALive 3517:Feel Good（单调栈 Grade C）
VJ题目链接
题意：
n个数，求区间[l,r] 使得 sum[l,r]*min(a[l],a[l+1],...,a[r]) 最大。若有多种答案，输出区间最短的。若还有多组，输出最先出现的。
思路：
求出a[i]为最小数时，最大的区间范围，即求a[i]的最左边的小于a[i]的位置，最右边的位置。
坑点：
因为要最小长度区间，当最小数是0的时候，就出现了巨大的坑点……所以特判。
代码：
#include <cstdio>#include <cstring>#include <cstdlib>#define N 100010int a[N];int l[N], r[N];long long sum[N];int n;int stk[N];void getl() { int top = 0; for (int i = 1; i <= n; i++) { while (top > 0 && a[stk[top-1]] >= a[i]) top--; stk[top++] = i; if (top == 1) l[i] = 0; else l[i] = stk[top-2]; }}void getr() { int top = 0; for (int i = n; i > 0; i--) { while (top > 0 && a[stk[top-1]] >= a[i]) top--; stk[top++] = i; if (top == 1) r[i] = n+1; else r[i] = stk[top-2]; }}int main() { int isfirst = 0; while (scanf("%d", &n) != EOF) { if (isfirst++) puts(""); //!isfirst++?:puts(""); sum[0] = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = a[i] + sum[i-1]; } sum[n+1] = sum[n]; getl(); getr(); long long ans = -1; int lans, rans; for (int i = 1; i <= n; i++) { long long now = (sum[r[i]-1]-sum[l[i]])*a[i]; if (ans < now) { ans = now; lans = l[i]+1; rans = r[i]-1; //This is a Great 坑 if (ans == 0) { lans = i; rans = i; } //The Great 坑 End } else if (ans == now) { if (rans-lans+1 > r[i]-l[i]-1) { lans = l[i]+1; rans = r[i]-1; } } } printf("%lld\n",ans); printf("%d %d\n", lans, rans); } return 0;}
UVALive 3517:Feel Good（单调栈 Grade C）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。