比赛:小奔的方案 solution

mac2022-06-30  121

题目

题目背景

有一个著名的题目:

五个海盗抢到了100个金币,每一颗都一样的大小和价值连城。 他们决定这么分: 1.抽签决定自己的号码 ------ [1、2、3、4、5] 2.首先,由1号提出分配方案,然后大家5人进行表决,当且仅当不少于半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。 3.如果1号死后,再由2号提出分配方案,然后大家4人进行表决,当且仅当不少于半数的人同意时,按照他的提案进行分配,否则将被扔入大海喂鲨鱼。 4.以次类推 每个海盗都是很聪明的人,他们遵循如下原则: 1.保命; 2.如果满足条件1,那么想办法获得更多的钱; 3.如果满足条件1,2,那么想办法杀更多的人。 那么最终的分配方案会是怎样的呢?

答案当然就是98,0,1,0,1。(注意这里是:不少于半数)

小奔合上书,来到了船头,突然发现真的有一群海盗!

小奔就这样被抓住了。。。

题目描述

NNN个海盗把他绑架到了海盗船上,开始准备瓜分他MMM个金币。

海盗们让小奔求出:若是NNN个海盗抢到了MMM个金币,并且要不少于QQQ%的人投赞成票,他们会如何分配呢?

请你给出NNN个海盗分MMM个金币且要不少于QQQ%的人投赞成票的解法,并保证结果号码较小的分到的金币尽可能的多。

每个数字间用一个空格隔开,如果结果中某个海盗死了,输出 −1-11 代替。

分析

本题可以参考海盗分金模型,倒着考虑,维护当前每个人分得的金币。可以发现第i个人自己得到的金币一定是i+1个人的金币数-1(有些数据不一定),分配的方法跟海盗分金一样,选出后面人数*q的人(要排序选择最好讨好的人)就可以了(同时维护号码较小的人所得金币越多)

代码

c++:

#include <cstdio> #include <cstring> using namespace std; int a[1001],b[1001],d[1001],f[1001]; int k,n,m,o; void zx(int p,int q)a { int i,j; i=0; while(((1.0*i)/(1.0*(q-p+1)))<(1.0*o/100)) { ++i; k=k+b[p+i-1]+1; if(i==1) --k; a[d[p+i-1]]=b[p+i-1]+1; if(a[d[p+i-1]]>m) a[d[p+i-1]]=m; } if(p+i-1==q) return; for(j=p+i;j<=q;++j) a[d[j]]=0; } void qsort(int l,int r) { int i,j,mid,p,m1; i=l; j=r; mid=b[(l+r)/2]; m1=d[(l+r)/2]; do { while(b[i]<mid||(b[i]==mid&&d[i]<m1)) ++i; while(b[j]>mid||(b[j]==mid&&d[j]>m1)) --j; if(i<=j) { p=b[i]; b[i]=b[j]; b[j]=p; p=d[i]; d[i]=d[j]; d[j]=p; ++i; --j; } }while(!(i>j)); if(l<j) qsort(l,j); if(i<r) qsort(i,r); } int main() { int i,j,c[1001]; scanf("%d%d%d",&n,&m,&o); for(i=n;i>=1;--i) { c[i]=i; memcpy(b,a,sizeof(b)); if(i!=n) for(j=n;j>=i+1;--j) f[j]=a[j]; memcpy(d,c,sizeof(d)); k=0; if(i!=n) qsort(i+1,n); memset(a,0,sizeof(a)); if(i!=n) zx(i,n); a[i]=m-k; if(a[i]<0) { for(j=n;j>=i+1;--j) a[j]=f[j]; a[i]=-1; } } for(i=1;i<=n;++i) printf("%d ",a[i]); return 0; }

Pascal:

var a,b,c,d,f:array[1..1000]of longint; i,j,k,n,m,o:longint; procedure zx(p,q:longint); var i,j:longint; begin i:=0; while (i/(q-p+1))<(o/100) do begin inc(i); k:=k+b[p+i-1]+1; if i=1 then dec(k); 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); 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; k:=0; if i<>n then qsort(i+1,n); fillchar(a,sizeof(a),0); if i<>n then zx(i,n); a[i]:=m-k; 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/10210049.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)