POJ 2796 Feel Good 【单调栈】
【题意】
给出n和a[1...n]，求出一对l，r使得sum[l, r] * min[l, r]最大。
【题解】
往两边单调栈求出第一个比当前小的数的位置。
然后随便做啦,O(n)
# include <stdio.h>
# include <iostream>
# include <string.h>
using namespace std;
int n, a[100100], last[100100], next[100100];
int st[100100], stn=0;
int stw[100100], l, r;
long long s[100100], maxx=-99999999;
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d", &a[i]);
s[i] = s[i-1] + a[i];
}
for (int i=1; i<=n; ++i) {
if(a[i] > st[stn]) {
st[++stn] = a[i];
last[i] = stw[stn-1];
stw[stn] = i;
} else {
while(a[i] <= st[stn] && stn != 0) --stn;
if(stn == 0) last[i] = 0;
else last[i] = stw[stn];
st[++stn] = a[i];
stw[stn] = i;
}
}
stn = 0;
memset(st, 0, sizeof(st));
memset(stw, 0, sizeof(stw));
for (int i=n; i>=1; --i) {
if(a[i] > st[stn]) {
st[++stn] = a[i];
next[i] = stw[stn-1];
stw[stn] = i;
} else {
while(a[i] <= st[stn] && stn != 0) --stn;
if(stn == 0) next[i] = n+1;
else next[i] = stw[stn];
st[++stn] = a[i];
stw[stn] = i;
}
}
for (int i=1; i<=n; ++i) {
//printf("%d %d\n", last[i], next[i]);
long long t = (long long)a[i] * (s[next[i]-1] - s[last[i]]);
if(t>maxx) {
maxx=t;
l=last[i]+1;
r=next[i]-1;
}
}
cout << maxx << endl;
cout << l << ' ' << r << endl;
return 0;
}
2022年9月20日 22:40
PUC Question Paper 2023 for Kar 1st & 2nd PUC Biology Model Paper 2023 Pdf Download with Answer Solutions for Theory, Objective type Multiple Choice Questions for Kannada Medium & English Medium students with important Questions. Kar PUC Biology Question Paper Biology is one of the most important subjects to Pre University Education (PUE) 1st and 2nd year Science stream students, and biology is a related subject of natural science, every student of PUC I & PUC II Science group Kannada medium and English medium student can download Karnataka 1st & 2nd Year PUC Biology Model Paper 2023.
2024年1月10日 13:50
Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.