8 条题解
-
2
C++:
#include
#include
#include
using namespace std;
int q[100001];
int a[100001];
int n,t;
int ll;
//int h[100001];
int l[100001];
int r[100001];
void make(int an[100001])
{ //int l=1;
ll=0; a[0]=-1; for(int i=1;i<=n;i++) { while(a[q[ll]]>=a[i]) { ll--; } an[i]=q[ll]; q[++ll]=i; }}
long long maxn;
int main()
{
while(scanf("%d",&n)) { if(n==0) { return 0; } for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } a[0]=-1; make(l); reverse(a+1,a+1+n); make(r); //int j=n; maxn=0; for(int i=1,j=n;i<=n;i++,j--) { maxn=max(maxn,a[i]*(n-l[j]-r[i]+1-(long long)(1))); // j--; } printf("%lld\n",maxn); }}
-
1
Wallacewwz
LV 3
@ 2024-1-27 11:46:22
因为对于一个高度 ， 我们往左边一直以这个高度延伸，直到不行，再往右边进行一样的操作
那么什么时候不行呢，就是当想要继续延伸的块高度比低
左边的极限就是 右边的极限就是
那么以 为原点往左右两边延伸的最大面积就是
我们使用单调栈即可求出 和 ，我们暂时记为 和
那么上述提到的面积就是 自己推导一下就知道了
AC CODE
#include <bits/stdc++.h> using namespace std; const long long N = 1e5+10,INF = 0x3f3f3f3f; long long a[N],ans[N],ans2[N],st[N],n,top,res,tmp; void calc1(){ for(long long i = 1; i <= n; i++){ while(top>0&&a[i]<=a[st[top]])top--; ans[i]=st[top];st[++top]=i; }//单调栈模版，但是>=改成<=以达到效果 } void calc2(){ for(long long i = n; i >= 1; i--){ while(top>0&&a[i]<=a[st[top]])top--; ans2[i]=st[top];st[++top]=i; }//单调栈模版，但是>=改成<=以达到效果 } void solve(){ cin >> n; if(n==0)exit(0); top = 0, res = 0, a[0]=a[n+1]=-INF; for(long long i = 1; i <= n; i++)cin >> a[i]; top = 0;st[++top]=0;calc1();//计算ans1 top = 0;st[++top]=n+1;calc2();//计算ans2 for(long long i = 1; i <= n; i++)res = max(res,(ans2[i]-ans[i]-1)*a[i]); cout << res << '\n'; } signed main(){ while(1+1==2)solve(); return 0; }//完美30行结束 -
1
c++
// #include<iostream> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; LL n, a[MAXN]; LL stack[MAXN]; LL l[MAXN], r[MAXN], top = 0; int main() { start:cin >> n; if(n == 0)return 0; for (int i = 0;i < n; i++) { cin >> a[i]; } top = 0; a[0] = -1; for(int i = 1;i <= n; i++) { while(top >= 0 && a[i] <= a[ stack[top - 1] ]) top--; l[i] = top == 0 ? 0 : (stack[top - 1] + 1); stack[top++] = i; } top = 0; a[0] = -1; for(int i = n - 1;i >= 0; i--) { while(top > 0 && a[i] <= a[ stack[top - 1] ]) top--; r[i] = top == 0 ? 0 : (stack[top - 1]); stack[top++] = i; } LL ans = 0; for(int i = 1;i <= n;i++){ //cout << l[i] << ' ' << r[i] << ' ' << a[i] << endl; ans = max(ans, (r[i] - l[i]) * a[i]); } cout << ans << endl; goto start; } -
1
C++ :
#include<iostream> #include<algorithm> #include<vector> #include<stack> using namespace std; typedef long long ll; const int N = 1e5 + 5; int n; int h[N], q[N], l[N], r[N]; void get(int bound[N]) { int tt = 0; h[0] = -1; for(int i = 1; i <= n; i ++ ){ while(h[q[tt]] >= h[i]) tt -- ; bound[i] = q[tt]; q[ ++ tt] = i; } } int main() { while(cin >> n, n){ for(int i = 1; i <= n; i ++ ) cin >> h[i]; //立一个标兵在队头 h[0] = -1; get(l); reverse(h + 1, h + n + 1); get(r); ll res = 0; //因为之前翻转了一下，所有原本的下标变成了对称位置的下标，1ll是long long 形式的1 for(int i = 1, j = n; i <= n; i ++, j -- ) res = max(res, h[i] * (n + 1 - l[j] - r[i] - 1ll)); cout << res << endl; } return 0; } -
0
jinhongxian LV 7 @ 2025-4-6 19:53:06
// #include #include #include #include using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; const int INF = 0x3f; LL n, a[MAXN]; LL stack[MAXN]; LL l[MAXN], r[MAXN], top = 0; int main() { start: cin >> n; if(n == 0)return 0; for (int i = 0; i < n; i++) { cin >> a[i]; } top = 0; a[0] = -1; for(int i = 1; i <= n; i++) { while(top >= 0 && a[i] <= a[ stack[top - 1] ]) top--; l[i] = top == 0 ? 0 : (stack[top - 1] + 1); stack[top++] = i; } top = 0; a[0] = -1; for(int i = n - 1; i >= 0; i--) { while(top > 0 && a[i] <= a[ stack[top - 1] ]) top--; r[i] = top == 0 ? 0 : (stack[top - 1]); stack[top++] = i; } LL ans = 0; for(int i = 1; i <= n; i++) { //cout << l[i] << ' ' << r[i] << ' ' << a[i] << endl; ans = max(ans, (r[i] - l[i]) * a[i]); } cout << ans << endl; goto start; }
-
0
思路:
我们找到左边第一个比他小和右边第一个比它小的,就可以得知这个高度的矩形的宽**代码:
#include<iostream> #include<stack> #define int long long using namespace std; stack<int> st; int h[100005],n,to,l[100005],r[100005],ans; signed main(){ while(cin>>n,n){ for(int i=1;i<=n;i++) cin>>h[i]; h[0]=-1; st.push(0); for(int i=1;i<=n;i++){ while(!st.empty()&&h[i]<=h[st.top()]) st.pop(); l[i]=st.top(); st.push(i); } while(!st.empty()) st.pop(); h[n+1]=-1; st.push(n+1); for(int i=n;i>=1;i--){ while(!st.empty()&&h[i]<=h[st.top()]) st.pop(); r[i]=st.top(); st.push(i); } ans=0; for(int i=1;i<=n;i++){ ans=max(ans,(r[i]-l[i]-1)*h[i]); } cout<<ans<<endl; } return 0; } -
-3
#include<cstdio> #include<stack> #include<iostream> #include<algorithm> using namespace std; int n,h[100000],ans=0,x; stack<int>st; bool va(int xx){ if(st.empty()){ return false; } else return st.top()>h[xx]; } int main(){ while(cin>>n &&n){ for(int i=1;i<=n;i++){ scanf("%d",&h[i]); } h[n+1]=-1; st.push(h[1]); for(int i=2;i<=n+1;i++){ x=0; while(va(i)){ x++; ans=max(x*st.top(),ans); st.pop(); } st.push(h[i]); } printf("%d\n",ans);} }本体思路太蒟蒻 -
-4
#include<stdio.h> #include<string.h> #include using namespace std; typedef long long ll; const int N = 1e5 + 5; ll l[N], r[N]; ll a[N]; int n; stack s; int main(){ while(scanf("%d",&n) && n){ while(!s.empty()) s.pop(); for(int i=1; i<=n; ++i){ scanf("%lld",&a[i]); l[i] = r[i] = i; } a[0] = a[n+1] = -1;
for(int i=1; i<=n; ++i){ while(!s.empty() && a[i] <= a[s.top()]) s.pop(); if(s.empty()) l[i] = 0; else l[i] = s.top(); s.push(i); } while(!s.empty()) s.pop(); for(int i=n; i>=1; --i){ while(!s.empty() && a[i] <= a[s.top()]) s.pop(); if(s.empty()) r[i] = n+1; else r[i] = s.top(); s.push(i); } ll sum, max = -1; for(int i=1; i<=n; ++i){ sum = (r[i] - l[i] - 1) * a[i]; if(sum > max) max = sum; } printf("%lld\n",max); } return 0;}
Gordon14
LV 6
@ 2022-1-19 16:08:02
- 1