t老师的做法好神……

题目描述

桌面上有 n 个水果，分别是苹果和橘子。Bytea需要从水果中选择连续的一个区间，并从左到右或从右到左拿水果，且过程中橘子的数量必须始终不小于苹果的数量。求最长的区间大小。

输入格式

第一行一个整数 n（$1 \le n \le 100000$），表示水果个数。 接下来一行共有 n 个字符$a_1, a_2, ..., a_n (a_i \in \{j,p\})$，分别表示苹果和橘子（波兰语）。

输出格式

输出一行共一个数字，表示最长的区间大小。

样例输入

6

jpjppj

样例输出

4

数据范围与提示

对于 $20\%$ 的数据，$n \le 1000$.
对于 $50\%$ 的数据，$n \le 10000$.
对于所有数据，$1 \le n \le 100000$.

题目分析

做法来源：「LOJ #2430」「POI2014」沙拉餐厅 Salad Baralad Bar

令$d_i$为$\sum_{x=1}^{i}\{[s_x=='p']-[s_x=='j']\}$，那么合法区间的充要条件就是$i \in (l,r), d_l \le d_i \le d_r$。（这个转化超级妙的）

那么用单调栈找到离以$i$为右端点区间的最近$l$，满足$d_l>d_i$，于是左端点就是$[l+1,r]$间$d_i$最小值的位置。

所以在单调栈过程中顺带维护以$i$为起点区间最小值的位置。有个小细节就是利用$f[0]=0$这么一个初值，来做相当于哨兵节点一样的作用，避免了$d_i<0$被判断合法。

感觉我单调栈并不熟练……

 #include<bits/stdc++.h>

 const int maxn = ;

 int n,ans,cnt,top,stk[maxn],d[maxn],f[maxn];

 char s[maxn];

 int main()

 {

     scanf("%d%s",&n,s+);

     for (int i=; i<=n; i++)

     {

         d[i] = d[i-]+(s[i]=='p'?:-);

         while (top&&stk[top] <= d[i])

         {

             if (d[f[top-]] > d[f[top]]) f[top-] = f[top];

             top--;

         }

         if (d[f[top]] <= d[i]) ans = std::max(ans, i-f[top]);

         stk[++top] = d[i], f[top] = i;

     }

     printf("%d\n",ans);

     return ;

 }

END

最新文章

  1. [译] C# 5.0 中的 Async 和 Await （整理中...）
  2. 敏捷软件开发VS传统软件工程
  3. 重温JSP学习笔记--与日期数字格式化有关的jstl标签库
  4. Crystal Report 遇到需要登录的问题
  5. JAVA经典算法40题（1-20）
  6. 反射给对象赋值遇到的问题——类型转换[转http://blog.csdn.net/xiaohan2826/article/details/8536074]
  7. SDRAM 控制器的解析
  8. 使用cocos2d 2.1制作一条河游戏(4): 主要的游戏逻辑BaseLayer设计
  9. ci公共模型类
  10. 【干货】Markdown编辑博文，公式图片轻松搞定
  11. [深度学习]实现一个博弈型的AI，从五子棋开始（1）
  12. PCI设备内存操作函数总结
  13. Spring源码情操陶冶-任务定时器ConcurrentTaskScheduler
  14. python之路--JavaScript
  15. SpringBoot使用WebJars
  16. javaScript中with函数用法实例分析
  17. activemq 安装 部署
  18. mysql数据库创建和权限分配
  19. cnblogs修改网站图标icon
  20. Python实现客观赋权法

热门文章

  1. P1308-道路修建 （noi 2011）
  2. 洛谷P2939 [USACO09FEB]改造路Revamping Trails
  3. 启动Eclipse时，出现 “Failed to load the JNI shared library &quot;C:\Program Files\java\jdk1.7.....\jvm.dll&quot;
  4. JS高级学习历程-11
  5. VUE中实现iview的图标效果时遇到的一个问题
  6. 长春理工大学第十四届程序设计竞赛（重现赛）B.Bowling Game
  7. ASM 磁盘组的的scrip
  8. Vsftp设置为PASV mode（被动模式传送）
  9. centos6.3搭建FTP服务器图文教程
  10. P3818 小A和uim之大逃离 II