分析：

此题是小奔的方案的改进。小奔的方案思路：倒推，每次都从小到大排序并且保证小号在前，然后使每一个人分到的金币都是上一次加一，直到金币分完或者自己可以存活（投票率大于等于所需概率），如果不行就-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.

巴特西

比赛：大奔的方案solution

分析：

代码：

最新文章

热门文章