51nod 1065:最小正子段和
2024-09-05 11:06:56
基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题
收藏
取消关注
N个整数组成的序列a[1],a[2],a[3],…,a[n],从中选出一个子序列(a[i],a[i+1],…a[j]),使这个子序列的和>0,并且这个和是所有和>0的子序列中最小的。
例如:4,-1,5,-2,-1,2,6,-2。-1,5,-2,-1,序列和为1,是最小的。
Input
第1行:整数序列的长度N(2 <= N <= 50000)
第2 - N+1行:N个整数
Output
输出最小正子段和。
Input示例
8
4
-1
5
-2
-1
2
6
-2
Output示例
1
对每一位来说,计算从第一位到该位置的数字的和。然后对这些和排序。
如果相近的位置上的node满足其pos的前后关系,就比较最小值,因为是相近的,所以已经是最小值候选了,其余的绝对不可能了,因为如果A到B不能形成队列,A到C形成队列了,那么B到C一定是比A到C的数值更小,而且还一定能够形成队列(A与B不能形成队列,说明posA>posB,A与C能形成队列,说明posA<posC,那就一定有posB<posC)。
这个题夹克老师太厉害了,膜拜~
另外自己还要注意一点的就是,以后一旦是连续序列这样的题目,自己第一时间需要想到的就是前缀和可能会发挥作用,碰到过好多次了还没有记性。
代码:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std; int n;
struct no1
{
long long value;
int pos;
}node[50005]; bool cmp(no1 &n1,no1 &n2)
{
return n1.value<n2.value;
} int main()
{
//freopen("i.txt","r",stdin);
//freopen("o.txt","w",stdout); int i,flag;
long long sum,temp,res;
scanf("%d",&n); node[0].pos=0;
node[0].value=0; sum=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&temp);
sum += temp; node[i].pos=i;
node[i].value=sum;
}
sort(node,node+n+1,cmp); flag=0;
for(i=1;i<=n;i++)
{
if(node[i].pos-node[i-1].pos>0&&node[i].value-node[i-1].value>0)
{
if(flag==0)
{
flag=1;
res=node[i].value-node[i-1].value;
}
else
{
if(node[i].value-node[i-1].value<res)
res=node[i].value-node[i-1].value;
}
}
}
printf("%lld\n",res); //system("pause");
return 0;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
最新文章
- Glide 图片加载库
- 遭遇flash播放mp3诡异问题
- Struts2 源码分析——过滤器(Filter)
- 清北学堂2017NOIP冬令营入学测试P4749 F’s problem(f)
- Listener-监听器+ServletContext+ApplicationContext
- [原]zoj3772--【水题】线段树区间查询+矩阵乘法
- Why Hadoop2
- 数据层使用DBHelper.dll来减少工作量
- Linux的环境变量总结
- 【C# -- OpenCV】Emgu CV 第一个实例
- Ansible系列(七):执行过程分析、异步模式和速度优化
- 【Bootstrap】 bootstrap-table表格组件
- 2017-2018-1 Java演绎法 第一周 作业
- String方法
- HTML <;script>; 标签的 defer 和 async 属性
- python笔记15-集合
- Spring Boot 解决方案 - 配置
- [luogu#2019/03/10模拟赛][LnOI2019]长脖子鹿省选模拟赛赛后总结
- springboot项目maven报错 LoggerFactory is not a Logback LoggerContext but Logback is on the classpath. Either remove Logback
- 【BZOJ3139】[HNOI2013]比赛(搜索)