比赛:大奔的方案solution
分析:
此题是小奔的方案的改进。小奔的方案思路:倒推,每次都从小到大排序并且保证小号在前,然后使每一个人分到的金币都是上一次加一,直到金币分完或者自己可以存活(投票率大于等于所需概率),如果不行就-1。 (即题目背景)
大奔的方案无非就是分两种情况:1.只讨好不是自己帮派的,那怕自己帮派成员都投反对票也能活下来。2.先讨好是自己帮派的(此时够了也要全部满足),然后如果不够就从小到大满足其他人。在这两种情况中选择一种(保证小号拿得多),就是答案。
代码:
(即使是Pascal,我也要排成c++的颜色
var
a,b,c,d,f,e:array[1..1000]of longint;
g:array[1..1000,1..1000]of boolean;
i,j,k1,k2,n,m,o,t,x,y,z:longint;
procedure zhx(p,q:longint);
var
i,j:longint;
s:real;
begin
i:=0;
s:=(o/100)*(q-p+1);
if trunc(s)<>s then s:=s+1;
j:=trunc(s);
for i:=p to q do if g[p,i] then begin dec(j); if p<>i then begin e[i]:=x; k2:=k2+x; end; end;
if j<=0 then exit;
i:=p;
while j>0 do
begin
inc(i);
if e[d[i]]<>0 then continue;
k2:=k2+b[i]+1;
e[d[i]]:=b[i]+1;
if e[d[p+i-1]]>m then e[d[p+i-1]]:=m;
dec(j);
end;
end;
procedure zx(p,q:longint);
var
i,j:longint;
begin
i:=0;
j:=0;
while (j/(q-p+1))<(o/100) do
begin
inc(i);
if i+p-1>q then begin k1:=maxlongint; exit; end;
if g[p,i+p-1] then continue;
inc(j);
k1:=k1+b[p+i-1]+1;
if i=1 then dec(k1);
a[d[p+i-1]]:=b[p+i-1]+1;
if a[d[p+i-1]]>m then a[d[p+i-1]]:=m;
end;
if (p+i-1)=q then exit;
for j:=p+i to q do a[d[j]]:=0;
end;
procedure qsort(l,r:longint);
var
i,j,mid,p,m1:longint;
begin
i:=l;j:=r;
mid:=b[(l+r) div 2];
m1:=d[(l+r) div 2];
repeat
while (b[i]<mid)or((b[i]=mid)and(d[i]<m1)) do inc(i);
while (b[j]>mid)or((b[j]=mid)and(d[j]>m1)) do dec(j);
if (i<=j) then
begin
p:=b[i]; b[i]:=b[j]; b[j]:=p;
p:=d[i]; d[i]:=d[j]; d[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
readln(n,m,o,t,x);
fillchar(f,sizeof(f),0);
fillchar(g,sizeof(g),false);
for i:=1 to t do
begin
readln(y,z);
if (f[y]<>0)and(f[z]<>0) then
begin
for j:=1 to n do if f[j]=f[z] then f[j]:=f[y];
continue;
end;
if (f[y]=0)and(f[z]=0) then begin f[y]:=y; f[z]:=f[y]; end
else begin f[y]:=f[z]+f[y]; f[z]:=f[y]; end;
end;
for i:=1 to n do for j:=1 to n do if (f[j]=f[i])and((f[j]<>0)or(i=j)) then g[i,j]:=true;
for i:=n downto 1 do
begin
c[i]:=i;
b:=a;
if i<>n then for j:=n downto i+1 do f[j]:=a[j];
d:=c;
k1:=0;
k2:=0;
if i<>n then qsort(i+1,n);
fillchar(a,sizeof(a),0);
fillchar(e,sizeof(e),0);
if i<>n then zx(i,n);
if i<>n then zhx(i,n);
e[i]:=m-k2;
a[i]:=m-k1;
j:=i;
while (e[j]=a[j])and(j<n) do inc(j);
if e[j]>a[j] then a:=e;
if a[i]<0 then
begin
for j:=n downto i+1 do a[j]:=f[j];
a[i]:=-1;
end;
end;
for i:=1 to n do write(a[i],' ');
end.