本文主要是介绍【UVA】1619-Feel Good（数据结构-栈），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
既然所有数都是大于等于0的，那么在一个区间最小值一定的情况下，这个区间越长越好（当然有特殊情况）对一个数a[i],left[i]代表左边第一个比它小的,right[i]代表右边第一个比它小的
如何构造left[i]呢？，从左往右构造一个单调递增的栈（一定是单调的！）
当a[i]比栈顶元素小的时候，栈顶元素出栈，（否则的话入栈，left[i]就是栈顶元素的位置，right数组同理可得
注意2个方面一个是栈空的时候的讨论，另外一个，如果写出来WA的话，试一下这组数据：
6
0 0 0 0 0 0
结果应该是
0
1 1
而不是
0
1 6
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100005;
int n;
stack<int>s;
LL arr[maxn];
int left[maxn],right[maxn];
LL sum[maxn];
void solve1(){while(!s.empty()) s.pop();for(int i = 1; i <= n; i++){LL e = arr[i];do{if(s.empty()){left[i] = 0;s.push(i);break;}LL c = arr[s.top()];if(c < e){left[i] = s.top();s.push(i);break;}else s.pop();}while(true);}
}
void solve2(){while(!s.empty()) s.pop();for(int i = n; i >= 1; i--){LL e = arr[i];do{if(s.empty()){right[i] = n + 1;s.push(i);break;}LL c = arr[s.top()];if(c < e){right[i] = s.top();s.push(i);break;}else s.pop();}while(true);}
}
int main(){int Case = 0;while(scanf("%d",&n) != EOF){sum[0] = 0L;for(int i = 1; i <= n; i++){scanf("%lld",&arr[i]);sum[i] = sum[i - 1] + arr[i];}solve1();solve2();LL ans = -1;int pos_x,pos_y;int l;for(int i = 1; i <= n; i++){int a = left[i];int b = right[i];int ll = (b - 1) - (a + 1);LL max_sum = (sum[b - 1] - sum[a]) * arr[i];if(max_sum > ans){pos_x = a + 1;pos_y = b - 1;l = pos_y - pos_x;ans = max_sum;}else if(max_sum == ans && ll < l){pos_x = a + 1;pos_y = b - 1;l = pos_y - pos_x;}}if(Case++) puts("");printf("%lld\n",ans);if(ans == 0)printf("%d %d\n",pos_x,pos_x);elseprintf("%d %d\n",pos_x,pos_y);}return 0;
}
这篇关于【UVA】1619-Feel Good（数据结构-栈）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
