本文主要是介绍最小正子段和 51Nod - 1065，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最小正子段和
题目链接：51Nod - 1065题意：找出一个连续的子序列， 使得子段和为正数， 找出最小的一个子段和；
这个题乍一看很熟悉， 有没有想起最大子段和那道题？？？！！！很兴奋吧， 动归？？？最大子段和是这样求得O(n)的复杂度；那么这个题一样吗？答案是否定的；
遇上这种连续序列的题多想一想前缀和；
思路是这样的：
求出前缀和，用结构体存， sum表示前缀和， id表示排序前该数的下标； 然后由小到大排序， 假设排完后是这样的： a0,a1, a2 ;
如果a0.id<a1.id<a2.id;那么答案一定在a0.sum, (a1.sum-a0.sum), (a2.sum-a1.sum)中；
如果不是顺序的， 即a0.id可能大于a1.id， 此时答案一定没有a1.id因为a0与a1之间的区间差为负；
我们比较相邻的两个前缀和， 如果前者的id小于后者的id那么两者sum差可能是一个答案；
为什么只比较相邻的两个？
还是上边的例子， 有a2.sum-a0.sum必定大于a2.sum-a1.sum;
注意前边最好加一个0；
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const long long INF = 0x3f3f3f3f;
struct node{long long sum;int id;
}a[50100];
bool cmp(node x, node y){return x.sum<y.sum;
}
int main(){int n;scanf("%d", &n);long long x;a[0].id=a[0].sum=0;//加上这个， 避免第一个数就是答案；for(int i=1; i<=n; i++){scanf("%lld", &x);a[i].sum=a[i-1].sum+x;a[i].id=i;}sort(a, a+n+1, cmp);long long ans=INF;for(int i=1; i<=n; i++){//答案是大于0的， 所以a[i].sum-a[i-1].sum>0不能丢掉；if(a[i].id>a[i-1].id&&a[i].sum-a[i-1].sum>0) ans=min(ans, a[i].sum-a[i-1].sum);}printf("%lld\n", ans);return 0;
}这篇关于最小正子段和 51Nod - 1065的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
