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