Gym - 101334F 单调栈

当时我的第一想法也是用单调栈，但是被我写炸了；我也不知道错在哪里；

看了大神的写法，用数组模拟的；

记录下单调递增栈的下标，以及每个数字作为最小值的最左边的位置。

当有数据要出栈的时候，说明栈里的数据已经不是最小了，右端点就是当前位置-1，那么就可以计算栈顶的元素所作的贡献；出栈完后，当前这个数字，他的最左边就是栈顶所能到达的位置；入栈；

#include <bits/stdc++.h>using namespace std;const int maxn = 100000 + 5; int a[maxn]; int stacks[maxn]; long long sum[maxn]; int lef[maxn];int main() {freopen("feelgood.in","r",stdin);freopen("feelgood.out","w",stdout);int n;scanf("%d",&n);memset(sum,0,sizeof(sum));memset(lef,0,sizeof(lef));for(int i=1;i<=n;i++) {scanf("%d",&a[i]);sum[i] = sum[i-1] + a[i];}a[++n] = -1;int top = 0;long long ans = -1;int ansl = 0,ansr = 0;for(int i=1;i<=n;i++) {if(top==0||a[i]>a[stacks[top-1]]) {stacks[top++] = i;lef[i] = i;continue;}if(a[i]==a[stacks[top-1]])continue;while(top>=1&&a[i]<a[stacks[top-1]]) {top --;long long tmp = (long long)a[stacks[top]]*(sum[i-1]-sum[lef[stacks[top]]-1]);if(tmp>ans) {ansr = i-1;ansl = lef[stacks[top]];ans = tmp;}}lef[i] = lef[stacks[top]];stacks[top++] = i;}printf("%lld\n%d %d\n",ans,ansl,ansr);return 0; } View Code

 

(之前的错误找到了ans=-1，可以都为0)

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int n; 6 const int maxn = 100000+5; 7 struct num { 8 long long value; 9 int maxleft,maxright; 10 int minleft,minright; 11 num():maxleft(1),maxright(1),minleft(1),minright(1){} 12 }a[maxn]; 13 14 stack<pair<int,int> > S; 15 16 long long sum[maxn]; 17 18 void getMax() 19 { 20 while(!S.empty()) 21 S.pop(); 22 S.push(make_pair(a[0].value,0)); 23 for(int i=1;i<n;i++) { 24 while(!S.empty()&&S.top().first<=a[i].value) { 25 //int value = S.top().first; 26 int key = S.top().second; 27 S.pop(); 28 29 a[i].maxleft +=a[key].maxleft; 30 if(!S.empty()) { 31 a[S.top().second].maxright +=a[key].maxright; 32 } 33 } 34 S.push(make_pair(a[i].value,i)); 35 } 36 while(!S.empty()) { 37 int key = S.top().second; 38 S.pop(); 39 if(!S.empty()) { 40 a[S.top().second].maxright +=a[key].maxright; 41 } 42 } 43 } 44 45 void getMin() 46 { 47 while(!S.empty()) 48 S.pop(); 49 S.push(make_pair(a[0].value,0)); 50 for(int i=1;i<n;i++) { 51 while(!S.empty()&&S.top().first>=a[i].value) { 52 //int value = S.top().first; 53 int key = S.top().second; 54 S.pop(); 55 56 a[i].minleft +=a[key].minleft; 57 if(!S.empty()) { 58 a[S.top().second].minright +=a[key].minright; 59 } 60 } 61 S.push(make_pair(a[i].value,i)); 62 } 63 while(!S.empty()) { 64 int key = S.top().second; 65 S.pop(); 66 if(!S.empty()) { 67 a[S.top().second].minright +=a[key].minright; 68 } 69 } 70 } 71 72 int main() 73 { 74 freopen("feelgood.in","r",stdin); 75 freopen("feelgood.out","w",stdout); 76 scanf("%d",&n); 77 for(int i=0;i<n;i++) { 78 scanf("%lld",&a[i].value); 79 sum[i+1] = sum[i] + a[i].value; 80 } 81 // getMax(); 82 getMin(); 83 84 int l = 0; 85 int r = 0; 86 long long ans = -1; 87 for(int i=0;i<n;i++) { 88 long long tmp = a[i].value*(sum[i+a[i].minright]-sum[i-a[i].minleft+1]); 89 if(ans<tmp) { 90 ans = tmp; 91 l = i - a[i].minleft + 2; 92 r = i + a[i].minright; 93 } 94 } 95 96 printf("%lld\n%d %d\n",ans,l,r); 97 98 return 0; 99 } View Code

 

转载于:https://www.cnblogs.com/TreeDream/p/6937770.html

总结

以上是生活随笔为你收集整理的Gym - 101334F 单调栈的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。