分析：

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

转载于:https://www.cnblogs.com/vercont/p/10210027.html

相关资源：大奔QQ群排名软件 v3.0.zip