C语言程序设计100例之（55）：游戏预言

本文主要是介绍C语言程序设计100例之（55）：游戏预言，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例55  游戏预言

题目描述

John和朋友们在玩纸牌游戏，他们一共有m个人（包括John）。他们的纸牌比较特殊，一共有n*m张牌，牌号分别为1,2,…,n*m，没有牌号相同的牌。每个人先拿到n张牌，然后，每一轮，每个人出一张牌，谁最大则谁赢得这一轮。现在已知John手中的n张牌，计算他最少能赢得多少轮。

输入格式

第一行为两个整数m和n，2≤m≤20，1≤n≤50；第二行有n个正整数，表示John手中的n张牌的数值。

输出格式

仅一个整数，表示John最少能赢的次数。

输入样例

2 5

1 7 2 10 9

输出样例

2

         （1）编程思路。

        定义数组int h[1001]={0};，其中h[i]=1表示牌号为i的牌在John手里，h[i]=0表示牌号为i的牌不在John手里。定义变量cnt表示其他人手里大牌的数量，初始值为0。

        用变量i从m*n 开始，从大到小枚举每一张牌，若当前这张牌i不在John手里，则这张牌作为一张大牌在其他人手里，cnt++；若这张牌在John手里，为了不让John赢，其他人应本着“能压一定压”的原则，此时若cnt>0，则有大牌可以压John的牌，用掉一张大牌压cnt--，若cnt==0，则没有大牌可压，这一轮中John所出的牌没人比他大，John赢，ans++。

        循环遍历结束后，ans的值即为John最少能赢的次数。

（2）源程序。

#include <stdio.h>

int main()

{

    int m,n;

    scanf("%d%d",&m,&n);

    int i,a;

    int h[1001]={0};

    for (i=1;i<=n;i++)

    {

        scanf("%d",&a);

        h[a]=1;

    }

    int cnt=0,ans=0;

    for (i=n*m;i>=1;i--)

    {

        if (h[i]==0) cnt++;

        else if(cnt>0) cnt--;

        else ans++;

    }

    printf("%d\n",ans);

   return 0;

}

习题55

55-1  山洞的灯

题目描述

已知n盏灯以及每盏灯的位置p[i]，p[i]均不相等，两盏相邻的灯当小于dist时，若这个安全距离里面还有灯是亮着时，就可以关掉该盏灯（即若第i-1盏与第i+1盏的距离<=dist，则可以关掉第i盏）。求在保证洞里的光线是充足的情况下，一段区域里能删除的灯的最大值。

距离洞口最近和最远的两盏灯必须是亮着。

输入格式

第一行两个数，n（n<=100000）和dist。

第二行n个数，即每盏灯的位置。

输出格式

一个数，即一段区域里能删除的灯的最大值。

输入样例

3 3

1 2 3

输出样例

1

         （1）编程思路。

        首先将山洞里的N盏灯按位置p[i]从小到大排序，显然，位置p[1]和p[n]处的灯分别是距离洞口最近和最远的两盏灯。

        利用变量i从2到n-1进行循环处理每盏灯，若p[i+1]-p[i-1]<=dist，则应该关闭p[i]处的灯，为了处理方便，置p[i]=p[i-1]，相当位置p[i]的灯移动到位置p[i-1]处，第i盏灯与第i-1盏灯合为一盏，也相当于删除了p[i]或关闭了第i盏灯。

       （2）源程序。

#include <stdio.h>

#include <algorithm>

using namespace std;

int main()

{

       int n,dist;

       scanf("%d%d",&n,&dist);

       int i,a[100005];

       for (i=1; i<=n; i++)

              scanf("%d",&a[i]);

       sort(a+1,a+1+n);

       int ans=0;

       for (i=2; i<=n-1; i++)

       {

              if(a[i+1]-a[i-1]<=dist)

              {

                     a[i]=a[i-1];

                     ans++;

              }

       }

    printf("%d\n",ans);

    return 0;

}

55-2  苹果树

题目描述

一个果园看起来像一张N*M的二维网格。在每个网格中，可以种植一棵苹果树来获得一个苹果，也可以施肥来加速相邻果树的生长。当网格施肥时，网格本身不会产生苹果，但其四棵相邻果树的苹果数量将增加一倍（如果存在的话）。例如，一棵苹果树位于（x，y），并且（x-1，y），（x，y-1）被施肥，而（x+1，y），（x，y+1）没有施肥，那么可以从（x，y）的苹果树上得到四个苹果。求在整个果园里最多能得到多少苹果？

输入

输入包含多个测试用例。测试用例数T（T<=100）出现在输入的第一行。

对于每个测试用例，在一行中给出两个整数N，M（1<=N，M<=100），表示果园的大小。

输出

对于每个测试用例，输出可以获得的最多苹果个数。

输入样例

2

2 2

3 3

输出样例

8

32

        （1）编程思路。

        在每个（i+j）%2==0  的格子上种树，其他的格子施肥就可以获得最多的苹果。

       （2）源程序。

#include <stdio.h>

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int ans=0;

        int n,m;

        scanf("%d%d",&n,&m);

        int i,j;

        for (i=0; i<n; i++)

            for (j=0; j<m; j++)

            {

                if((i+j)%2==0)

                {

                    int temp=1;

                    if (i-1>=0)  temp*=2;

                    if (i+1<n)  temp*=2;

                    if (j-1>=0) temp*=2;

                    if (j+1<m)  temp*=2;

                    ans+=temp;

                }

            }

        printf("%d\n",ans);

    }

    return 0;

}

55-3  倒水

题目描述

一天，小强买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着小强发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的瓶子）

显然在某些情况下小强无法达到目标，比如N=3，K=1。此时小强会重新买一些新的瓶子（新瓶子容量无限，开始时有1升水），以到达目标。

现在CC想知道，最少需要买多少新瓶子才能达到目标呢？

输入格式

一行两个正整数， N,K(1≤N≤2×10⁹ ,K≤1000)。

输出格式

一个非负整数，表示最少需要买多少新瓶子。

输入样例

3 1

输出样例

1

         （1）编程思路。

        水瓶的合并是用2个含水量相同的瓶子进行合并而来。初始时，n个有水的瓶子，最后合并成的瓶子个数，就是n这个数对应二进制数中1的个数。

        例如，n=12，初始时12个各含1升水的瓶子，两两合并得到6个各含2升水的瓶子，再两两合并得到3个各含4升水的瓶子，最后将其中两个瓶子合并含8升水。最后，得到两个瓶子，1个含8升水，1个含4升水。n=12对应二进制数为1100，1的个数为2。若要最后瓶子的个数为1个，显然需要增加含1升水的瓶子，在n的最后1个1的位置加个1，会进位，从而1的个数会减少（或不变），从而减少瓶子数。1100在最后一个1的位置加上1（实际加上了4）后，变成10000，即剩下1个瓶子。

        因此，要保留不超过K个瓶子，只要N加上新瓶子的总数对应二进制数中1的个数不超过K即可。

       （2）源程序。

#include <stdio.h>

int bitCount(int x)

{

    int cnt=0;

    while (x!=0)

    {

        cnt++;

        x=x&(x-1);

    }

    return cnt;

}

int main()

{

    int n, k, ans=0;

    scanf("%d%d", &n, &k);

    while (bitCount(n) > k)

    {

        ans += n & (-n);   // n&(-n) 表示n对应二进制数的最后一个1

        n += n & (-n);

    }

    printf("%d\n",ans);

   return 0;

}

这篇关于C语言程序设计100例之（55）：游戏预言的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！