不是说好的20s吗，怎么我19s都超时……逗我
最后还得写成c++才能过……
首先不难发现询问肯定是O(1）的复杂度
我们先把奇数和偶数分开排序，不难发现几个性质
1. 奇数的个数一定是奇数
2. 奇数选取随k成单调增
然后就能在O(n)的时间预处理了……
1 type arr=array[0..1000010] of int64; 2 var a,b,f:arr; 3 j,i,n1,n2,n,m,x:longint; 4 ch:boolean; 5 6 procedure qsort(var a:arr;n:longint); 7 procedure sort(l,r: longint); 8 var i,j: longint; 9 x,y:int64; 10 begin 11 i:=l; 12 j:=r; 13 x:=a[(l+r) div 2]; 14 repeat 15 while a[i]>x do inc(i); 16 while x>a[j] do dec(j); 17 if not(i>j) then 18 begin 19 y:=a[i]; 20 a[i]:=a[j]; 21 a[j]:=y; 22 inc(i); 23 j:=j-1; 24 end; 25 until i>j; 26 if l<j then sort(l,j); 27 if i<r then sort(i,r); 28 end; 29 30 begin 31 sort(1,n); 32 end; 33 34 begin 35 readln(n); 36 for i:=1 to n do 37 begin 38 read(x); 39 if x mod 2=1 then 40 begin 41 inc(n1); 42 a[n1]:=x; 43 end 44 else begin 45 inc(n2); 46 b[n2]:=x; 47 end; 48 end; 49 qsort(a,n1); 50 qsort(b,n2); 51 for i:=1 to n1 do 52 a[i]:=a[i-1]+a[i]; 53 for i:=1 to n2 do 54 b[i]:=b[i-1]+b[i]; 55 if n1=0 then 56 f[1]:=-1 57 else f[1]:=a[1]; 58 i:=1; 59 j:=1; 60 while i<n do 61 begin 62 inc(i); 63 f[i]:=-1; 64 while (i-j>n2) and (j<=n1) do j:=j+2; 65 ch:=false; 66 while (j<=n1) and (i-j>=0) and (f[i]<a[j]+b[i-j]) do 67 begin 68 f[i]:=a[j]+b[i-j]; 69 j:=j+2; 70 ch:=true; 71 end; 72 if ch then j:=j-2; 73 end; 74 readln(m); 75 for i:=1 to m do 76 begin 77 readln(x); 78 writeln(f[x]); 79 end; 80 end.
