做网站能赚钱么,腾讯企业邮箱登录入口忘记密码,无忧网站建设服务,泛解析对网站的影响题干#xff1a;
N个整数组成的序列a11,a22,a33,…,ann#xff0c;从中选出一个子序列#xff08;aii,ai1i1,…ajj#xff09;#xff0c;使这个子序列的和0#xff0c;并且这个和是所有和0的子序列中最小的。
例如#xff1a;4#xff0c;-1#xff0c;5
N个整数组成的序列a11,a22,a33,…,ann从中选出一个子序列aii,ai1i1,…ajj使这个子序列的和0并且这个和是所有和0的子序列中最小的。
例如4-15-2-126-2。-15-2-1序列和为1是最小的。
Input
第1行整数序列的长度N2 N 50000) 第2 - N1行N个整数
Output
输出最小正子段和。
Sample Input
8
4
-1
5
-2
-1
2
6
-2
Sample Output
1
题目大意 中文题不解释啦。
解题报告 法一可以用结构体保存一个前缀和然后对前缀和排序可以证明答案就在相邻的两个排序中。当然要满足输入顺序不能改变即node[i].pos node[i-1].pos node[i].sum node[i-1].sum 这两个条件都需要满足。并且 这里pos放在结构体里并且带着这个pos排序不能求完前缀和然后用pos数组存sum[i]出现的位置因为可能有多个sum[i]是同一个值会重叠而且此法不能去重所以需要带着pos这个值排序。 还有一个细节这里的排序必须从node开始排序而不是node1 也很好理解因为答案也可能就是输入的sum[i]前缀和所以sum[i] - sum[0]也可能是答案啊还有就是注意这题需要longlong。 法二可以用线段树。 附一个题解
将前n项和求出来并排序然后比较相邻两项其位置关系如果可以组成序列则说明其可能是所要求结果然后从所有可能是结果的结果中取出最小值即可。 如
排序前
sum4386571311pos12345678
排序后
sum3456781113pos21546387
如果ABC为排序后的结果那么当A和B不能组成序列而A和C可以组成序列时那么B和C一定可以组成序列并且BC一定会比AC更优。链接
AC代码前缀和排序
#includebits/stdc.h
using namespace std;
const int MAX 50000 5;
int a[MAX];
int n;
struct Node {int pos,val;long long sum;
} node[MAX];
bool cmp(Node a,Node b){return a.sum b.sum;
}
int main()
{cinn;for(int i 1; in; i) {scanf(%d,node[i].val);node[i].pos i;node[i].sum node[i-1].sum node[i].val;}
// for(int i 1; in; i) {
// printf(%d %d %d %d\n,i,node[i].pos,node[i].sum,node[i].val);
// }// printf(\n);sort(node,noden1,cmp);
// for(int i 1; in; i) {
// printf(%d %d %d %d\n,i,node[i].pos,node[i].sum,node[i].val);
// }long long minn 0x3f3f3f3f3f3f3f3f;int flag 1;int pos 1;while(node[pos].pos node[pos - 1].pos) pos;for(int i 1; in; i) {if(node[i].pos node[i-1].pos node[i].sum node[i-1].sum) {minn min(minn,node[i].sum - node[i-1].sum);}}printf(%lld\n,minn);return 0 ;
}
法二用set维护一下。
