题目

题目背景

有一个著名的题目：



五个海盗抢到了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.

巴特西

比赛：小奔的方案 solution

题目

题目背景

题目描述

分析

代码

c++：

Pascal：

最新文章

热门文章