一道随机算法的题目
随便用什么随机算法
首先我们可以想到枚举类型3的最终类型，然后再做
先贪心出一个较优的序列，首先我们知道肯定是在A机器上先做完类型1的事件再做类型2的事件，机器B也类似，因为这些没有等待时间，而他们做完了后续事情才能做
然后对类型1进行排序，按timeb为第一关键字降序（为了填补空隙，前面的越大排得就越紧密），按timea为第二关键字升序排序（尽量早点让类型1的B机器上的事先做），类型2的也类似
然后随机2000次左右（每次随机交换类型1的两个和类型2的两个）正确率就很高了
const
maxn=;
inf=;
type
node=record
kind,a,b,time:longint;
end;
var
a:array[..maxn]of node;
aa,bb,sa,sb:array[..maxn]of longint;
n,ans,ta,tb,numa,numb,suma,sumb:longint; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; procedure init;
var
i:longint;
begin
read(n);
for i:= to n do
with a[i] do
read(kind,a,b);
ans:=inf;
end; function geta:boolean;
var
k:longint;
begin
if numa>n then exit(false);
if numa>suma then k:=bb[numa-suma]
else k:=aa[numa];
if (a[k].kind=) or (a[k].time>) then
begin
ta:=max(ta,a[k].time)+a[k].a;
a[k].time:=ta;
inc(numa);
exit(true);
end;
exit(false);
end; function getb:boolean;
var
k:longint;
begin
if numb>n then exit(false);
if numb>sumb then k:=aa[numb-sumb]
else k:=bb[numb];
if (a[k].kind=) or (a[k].time>) then
begin
tb:=max(tb,a[k].time)+a[k].b;
a[k].time:=tb;
inc(numb);
exit(true);
end;
exit(false);
end; procedure get;
var
i,j,lastans:longint;
begin
suma:=;
sumb:=;
lastans:=inf;
for i:= to n do
if a[i].kind= then
begin
inc(suma);
sa[suma]:=i;
end
else
begin
inc(sumb);
sb[sumb]:=i;
end;
for i:=suma downto do
for j:= to i- do
if (a[sa[j+]].b>a[sa[j]].b) or ((a[sa[j+]].b=a[sa[j]].b) and (a[sa[j+]].a<a[sa[j]].a)) then swap(sa[j],sa[j+]);
for i:=sumb downto do
for j:= to i- do
if (a[sb[j+]].a>a[sb[j]].a) or ((a[sb[j+]].a=a[sb[j]].a) and (a[sb[j+]].b<a[sb[j]].b)) then swap(sb[j],sb[j+]);
for j:= to do
begin
aa:=sa;
bb:=sb;
if suma<> then
swap(aa[random()mod suma+],aa[random()mod suma+]);
if sumb<> then
swap(bb[random()mod sumb+],bb[random()mod sumb+]);
for i:= to n do
a[i].time:=;
ta:=;
tb:=;
numa:=;
numb:=;
while (numa<=n) or (numb<=n) do
begin
if ta<tb then
begin
if geta=false then getb;
end
else
if getb=false then geta;
end;
if lastans>=max(ta,tb) then
begin
lastans:=max(ta,tb);
ans:=min(lastans,ans);
sa:=aa;
sb:=bb;
end;
end;
end; procedure try(x:longint);
begin
if x=n+ then get
else
if a[x].kind= then
begin
a[x].kind:=;
try(x+);
a[x].kind:=;
try(x+);
a[x].kind:=;
end
else try(x+);
end; begin
randomize;
init;
try();
write(ans);
end.