【数据结构】 CF 547B Mike and Feet

前端之家收集整理的这篇文章主要介绍了【数据结构】 CF 547B Mike and Feet前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

点击打开链接

长度为n的一个数列

定义 一个区间内的 最小的值为 这个区间的strength

求长度为 1-n 的区间 最大的strength

先求出每个位置左边/右边 的比它小的值的位置

这样在 L+1 R-1 区间内这个位置是最小值

然而 区间[len]的值是小于等于区间[len-1]

即可以推出


  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int MAXN = 200009;//点数的最大值
  5. const int MAXM = 604000;//边数的最大值
  6. const LL INF = 1<<30;
  7. const LL mod= 1000000007;
  8. #define lson l,m,rt<<1
  9. #define rson m+1,r,rt<<1|1
  10. int low[MAXN],hig[MAXN],a[MAXN],ans[MAXN];
  11. int main()
  12. {
  13. int n;
  14. cin>>n;
  15. stack<int>st;
  16. for(int i=1;i<=n;i++)
  17. {
  18. ans[i]=0;
  19. cin>>a[i];
  20. }
  21. while(!st.empty()) st.pop();
  22. for(int i=1;i<=n;i++)
  23. {
  24. while(!st.empty()&&a[st.top()]>=a[i])
  25. st.pop();
  26. if(st.empty()) low[i]=0;
  27. else low[i]=st.top();
  28. st.push(i);
  29. }
  30. while(!st.empty()) st.pop();
  31. for(int i=n;i>=1;i--)
  32. {
  33. while(!st.empty()&&a[st.top()]>=a[i])
  34. st.pop();
  35. if(st.empty()) hig[i]=n+1;
  36. else hig[i]=st.top();
  37. st.push(i);
  38. }
  39. for(int i=1;i<=n;i++)
  40. {
  41. int len=hig[i]-low[i]-1;
  42. ans[len]=max(ans[len],a[i]);
  43. }
  44. ans[n+1]=0;
  45. for(int i=n;i>=0;i--)
  46. ans[i]=max(ans[i],ans[i+1]);
  47. for(int i=1;i<=n;i++)
  48. printf("%d ",ans[i]);
  49. return 0;
  50. }

猜你在找的数据结构相关文章