首页 > 代码库 > 最小和(min)

最小和(min)

2024-08-19 12:57:36   222人阅读

技术分享

题目描述：
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)


联系
我们