首页 > 代码库 > 最小和(min)
最小和(min)
题目描述:
N 个数排成一排,你可以任意选择连续的若干个数,算出它们的和。问该如何选择才能
使得和的绝对值最小。
如:N=8 时,8个数如下:
1 2 3 4 5 6 7 8
-20 90 -30 -20 80 -70 -60 125
如果我们选择1到 4这4个数,和为20,还可以选择 6到 8这 3个数,和为-5,|-5|=5,
该方案获得的和的绝对值最小。
输入格式:
第一行输入N,表示数字的个数。接下来N 行描述这N 个数字。
输出格式:
第一行输出一个整数,表示最小绝对值的和,第二行包含一个整数表示形成该绝对值
和最长序列的长度。
数据说明:
40%的数据 N<=4000
对于许多数据,最长序列的长度唯一。
100%的数据 N<=100000,|每个数字的值|<=10^10
输入:
8
-20
90
-30
-20
80
-70
-60
125
输出:
5
3
思路:1:暴力枚举,枚举首端点,尾端点,然后用O(n)的时间算出和,时间复杂度O(n^3);炸破天际
2:优化方法一,运用前缀和思想,用O(1)算出L到R的和,总时间O(n^2); 好像还是不行。
3:正解:思考方案2,对于每个R,我们要找到一个L使L的前缀和-R的前缀和最小,然后,我们想要快速找到,
想一下,对于一个序列,怎样的两个数相减的绝对值最小?显然,是大小相邻的两个数,因为如果中间隔了数,一定不如大小相邻的数优
有了这样的思想,我们可以将求得的前缀和数组排序,然后,相邻两数两两相减,这样,用O(1)的时间复杂度就可以算出结果。
1 program ex01; 2 var a,f,pl:array[0..100100] of int64; 3 n,ans,ll:int64; 4 function max(a,b:longint):longint; 5 begin 6 if a>b then exit(a); 7 exit(b); 8 end; 9 function min(a,b:longint):longint; 10 begin 11 if a<b then exit(a); 12 exit(b); 13 end; 14 procedure init; 15 var i:longint; 16 begin 17 readln(n); 18 for i:=1 to n do 19 begin 20 readln(a[i]); 21 f[i]:=f[i-1]+a[i]; 22 pl[i]:=i; 23 end; 24 end; 25 procedure qsort(l,r:longint); 26 var i,j,p,mid:int64; 27 begin 28 i:=l; j:=r; mid:=f[(i+j) div 2]; 29 repeat 30 while f[i]<mid do inc(i); 31 while f[j]>mid do dec(j); 32 if i<=j then 33 begin 34 p:=f[i]; f[i]:=f[j]; f[j]:=p; 35 p:=pl[i]; pl[i]:=pl[j]; pl[j]:=p; 36 inc(i); dec(j); 37 end; 38 until i>j; 39 if i<r then qsort(i,r); 40 if l<j then qsort(l,j); 41 end; 42 procedure doit; 43 var i:longint; 44 begin 45 ans:=maxlongint; 46 for i:=2 to n+1 do 47 begin 48 if abs(f[i]-f[i-1])=abs(ans) then 49 if max(pl[i],pl[i-1])-min(pl[i],pl[i-1])>ll then 50 ll:=max(pl[i],pl[i-1])-min(pl[i],pl[i-1]); 51 if abs(f[i]-f[i-1])<abs(ans) then 52 begin 53 ans:=abs(f[i]-f[i-1]); 54 ll:=max(pl[i],pl[i-1])-min(pl[i],pl[i-1]); 55 end; 56 end; 57 end; 58 procedure print; 59 begin 60 writeln(ans); 61 writeln(ll); 62 end; 63 begin 64 init; 65 qsort(1,n+1); 66 doit; 67 print; 68 69 end.
最小和(min)