0

我有一个关于数字序列的作业。给定从1到MAX的n 个元素数组。我们可以选择任何数字成为开始。我们可以将start乘以2，或者将其除以 2，但如果 start 已经是奇数，我们就不能将它除。任务是我们必须最小化数组中每个数字的差异总和。 例如 arr[]={2,4,7,32,16} 输出为 1，因为我们可以选择 1 作为开始。对于每个元素，我们必须使这个数字更大并且更接近元素。 我们遍历数组。 对于 n=0；元素是 2。所以我们将start乘以2，1 次start=2





所以差是2-2=0；
对于 n=1；元素是 4。所以我们将start乘以2，1 次start=4，所以差是 4-4=0；
对于 n=2；元素是 7。所以我们将start乘以2，1 次start=8，所以差值是 8-7=1；
对于 n=3；元素是 32。所以我们将start乘以2，2 次start=32所以差是 32-32=0；
对于 n=4；元素是16。所以我们将start除以2，1次start=16，所以差是16-16=0；所以总差异=0+0+1+0=1；

如果我们选择 start=3 那么它就变成
For n=1; 元素是 4。所以我们乘以startby 2, 1 time start=6所以差是 6-4=2;
对于 n=2；元素是 7。所以我们将start乘以2，1 次start=12，所以差值是 12-7=5；
对于 n=3；元素是 32。所以我们将start乘以2，2 次start=48所以差是 48-32=16；
对于 n=4；元素是16。所以我们把start除以2，1次start=24，所以差是24-16=8；所以总差异=2+5+16+8=31；

我们可以看到，对于start=1 ，通过将每个数字从1强制强制为MAX，输出比所有数字都最小。

为了解决这个问题，我有了主意。

  1. 首先，我们选择从1到MAX的所有奇数。
  2. 然后我暴力破解每个元素的所有可能开始以获得最小值。

这是帕斯卡代码

uses math;
var
data:array[1..1000100] of longint;
s:string[7];
n,i,j,min,ansn,ansb,sub:longint;

function minimum(a,b:longint):longint;
begin
if a>b then
minimum:=b
else
minimum:=a;
end;

function hitung(a:longint):longint;
var
x,hit,ca,tot,b:longint;

begin
hit:=0;
tot:=0;
for x:=1 to n do begin
hit:=hit+data[x];

b:=a;

while b<data[x] do begin
b:=b*2;
end;

tot:=tot+b;
end;
hitung:=tot-hit;
end;

begin
readln(s);
readln(n);
sub:=1000000;
for i:= 1 to n do
read(data[i]);

ansb:=hitung(1);

j:=1;

while ((ansb>0) and (j<=sub)) do
begin
ansn:=hitung((2*(j))+1);
min:=minimum(ansb,ansn);
ansb:=min;
j:=j+1
end;

writeln(min);
end.

它适用于小MAX，但解决方案的提示说该解决方案使用前缀和，O（MAX / 2）。虽然我的解决方案是 O( MAX /2*N)。我不知道在哪里插入前缀总和。我们怎么能做到这一点？提前致谢！

4

0 回答 0