做法是,先求出前缀和pre。然后枚举端点i,[i+1,n]中pre最小的找出来,减去pre[i-1]大于0,这是第一个条件;第二个条件是,从i开始的后缀和和i之前的最小的一个pre相加大于0。只要满足这两个条件那么这个端点就是可行的。显然找这两个区间的最值都是可以用数组线性维护的,因此总体复杂度是O(n)的。

  代码如下:

 #include <stdio.h>
#include <algorithm>
#include <algorithm>
using namespace std;
const int N = 2e5 + ; int a[N];
int pre[N],suf[N];
int min_pre_qian[N],min_pre_hou[N]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",a+i),pre[i] = pre[i-] + a[i];
if(i == ) min_pre_qian[i] = pre[];
else min_pre_qian[i] = min(pre[i], min_pre_qian[i-]);
}
suf[n+] = ;
for(int i=n;i>=;i--)
{
suf[i] = suf[i+] + a[i];
if(i == n) min_pre_hou[i] = pre[i];
else min_pre_hou[i] = min(min_pre_hou[i+], pre[i]);
//min_suf[i] = min(suf[i], min_suf[i+1]);
}
int ans = ;
for(int i=;i<=n;i++)
{
//printf("%d %d %d %d %d ??\n",i,min_pre_hou[i],pre[i-1],suf[i],max_pre_qian[i-1]);
if(min_pre_hou[i] - pre[i-] > && suf[i] + min_pre_qian[i-] > )
{
ans++;
}
}
printf("%d\n",ans);
}
}

最新文章

  1. MySQL大小写补坑记
  2. YACC和BISON学习心得
  3. python中的动态变量
  4. HttpURLConnection GET/POST写法
  5. Spring集成PageHelper的简单用法
  6. Oracle 行拼接 wmsys.wm_concat扩展
  7. style currentStyle getComputedStyle的区别和用法
  8. python几个排序函数 sort sorted argsort
  9. 简洁、轻量的前端UI框架 - Hbook
  10. ThinkPHP 前台视图实现类似于Yii的自动验证
  11. Solr(五)Solr实现简单的类似百度搜索高亮功能-2代码
  12. hdu 5442 (后缀数组)
  13. mysql生成日期的辅助表
  14. 使用Github时遇到问题的解决方法
  15. 关于Xocd升级 cocopoads无法使用的解决
  16. Ubuntu安装设置nginx和nohup常用操作
  17. JavaScript大杂烩4 - 理解JavaScript对象的继承机制
  18. SCCM2012理论知识详解
  19. ionic 2.x 3.x input触发调用键盘搜索及事件
  20. Arduino入门笔记(7):利用1602、1302实现时钟和定时器

热门文章

  1. 三种TCP协议聊天室实现
  2. 雷达无线电系列(二)经典CFAR算法图文解析与实现(matlab)
  3. SQL 语句使用关键字错误
  4. 如何在含有json类型的字段上建立多列索引
  5. stm32 窗口看门狗 WWDG
  6. JS 百度地图 换地图主题颜色(API自带)
  7. Spring3.2.2中相关Jar包的作用
  8. 《流畅的Python》Data Structures--第7章 colsure and decorator
  9. linux实操_shell判断语句
  10. MyBankgon功能