题目
题目背景
有一个著名的题目:
五个海盗抢到了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-1−1 代替。
分析
本题可以参考海盗分金模型,倒着考虑,维护当前每个人分得的金币。可以发现第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上百实例源码以及开源项目