首页 > 代码库 > 最小和(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)