C语言程序设计100例之（19）：欢乐的跳

例19   欢乐的跳

题目描述

一个n个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了[1,n-1]之间的所有整数，则称之符合“欢乐的跳”，如数组1 4 2 3符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数n(1≤n≤1000)开始，接下来n个空格隔开的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出"jolly"，否则输出"not jolly"。

输入样例 #1

4 1 4 2 3

输出样例 #1

jolly

输入样例 #2

5 1 4 2 -1 6

输出样例 #2

not jolly

        （1）编程思路。

        为了判断数组两个连续元素之间差的绝对值是否包括了[1,n-1]之间的所有整数，定义一个数组int hash[1001]，其中hash[i]=0表示整数i未出现，hash[i]=1表示整数i出现过。初始时，hash数组的全部元素值均为0。

        对n个元素的数组a，用循环for (i=1;i<n;i++)对数组中连续两个元素的差的绝对值d（d=abs(a[i]-a[i-1])）进行处理。若差的绝对值d小于n，则置hash[d]=1，表示整数d出现了。

        之后，判断数组hash的情况，若数组元素hash[1]~hash[n-1]的值全为1，则表示数组a中两个连续元素之间差的绝对值包括了[1,n-1]之间的所有整数。

        （2）源程序。

#include <stdio.h>

#include <math.h>

int main()

{

    int hash[1001]={0},a[1001],n,i,d;

    scanf("%d",&n);

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

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

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

    {

        d=abs(a[i]-a[i-1]);

        if (d<=n-1) hash[d]=1;

    }

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

        if (hash[i]==0) break;

    if (i<n)

                   printf("not jolly\n");

    else

                   printf("jolly\n");

    return 0;

}

习题19

19-1  校门外的树

        本题选自洛谷题库 （https://www.luogu.org/problem/p1047）

题目描述

某校大门外长度为l的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在l的位置；数轴上的每个整数点，即0,1,2,…,l，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有2个整数l((1≤l≤10000)和 m(1≤m≤100)，l代表马路的长度，m代表区域的数目，l和m之间用一个空格隔开。

接下来的m行每行包含2个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式

1个整数，表示马路上剩余的树的数目。

输入样例

500 3

150 300

100 200

470 471

输出样例

298

        （1）编程思路。

        定义数组int f[10001]，其中f[i]=1表示坐标为i的位置有一棵树，f[i]=0表示坐标为i的位置的树被移走了。初始时，数组的元素f[0]~f[l]全部置为1，表示长度为l的马路上每间隔1米有一棵树。

        每输入一组区域的起始点和终止点的坐标begin和end，就将f[begin]~f[end]之间的数组元素的值修改为0，表示树被移走了。

        最后，统计数组f中值为1的元素的个数，就是马路上剩余的树的数目。

        （2）源程序。

#include <stdio.h>

int main()

{

    int l,m,begin,end,i,cnt;

    int f[10001];

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

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

        f[i]=1;

    while (m--)

    {

        scanf("%d%d",&begin,&end);

        for (i=begin;i<=end;i++)

            f[i]=0;

    }

    cnt=0;

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

    {

       if (f[i]==1)

          cnt++;

    }

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

    return 0;

}

19-2  校门外的树（增强版）

        本题选自洛谷题库 （https://www.luogu.org/problem/p1276）

题目描述

校门外马路上本来从编号0到l，每一编号的位置都有1棵树。有砍树者每次从编号a到b处连续砍掉每1棵树，就连树苗也不放过（记 0 a b ，含a和b）；幸运的是还有植树者每次从编号c到d 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 c d，含c和d）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

输入格式

第一行l和n，表示校园外原来有l+1棵树，并有n次砍树或种树的操作。

以下n行，砍树或植树的标记和范围，每行3个整数。

l（1 <= l <= 10000）和 n（1 <= n <= 100）

输出格式

共两行。第1行校门外留下的树苗数目，第2行种上又被拔掉的树苗数目。

输入样例

10 3

0 2 6

1 1 8

0 5 7

输出样例

3

2

        （1）编程思路。

        本题思路与上题类同。同样定义数组int f[10001]，其中f[i]=1表示坐标为i的位置有一棵树，f[i]=2表示坐标为i的位置补种了一颗树苗，f[i]=0表示坐标为i的位置的树或树苗被移走了。初始时，数组的元素f[0]~f[l]全部置为1，表示长度为l的马路上每间隔1米有一棵树。

        程序中根据砍树或种树的操作对数组f的相应元素进行处理。具体见源程序。

       （2）源程序。

#include <stdio.h>

int main()

{

    int l,n,m,begin,end,i,cnt1,cnt2;

    int f[10001];

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

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

        f[i]=1;       // 初始为一棵树

    cnt2=0;          // 种上又被砍掉的树苗数

    while (n--)

    {

        scanf("%d%d%d",&m,&begin,&end);

        if (m==0)    // 砍树或树苗

        {

            for (i=begin;i<=end;i++)

            {

                if (f[i]==2)  cnt2++;   // 树苗被砍掉了

                f[i]=0;

            }

        }

        else        // 种树苗

        {

             for (i=begin;i<=end;i++)

                 if (f[i]==0)

                    f[i]=2;

        }

    }

    cnt1=0;         // 留下的树苗数

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

    {

       if (f[i]==2)

          cnt1++;

    }

    printf("%d\n%d\n",cnt1,cnt2);

    return 0;

}

19-3  珠心算测验

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

输入格式

共两行，第一行包含一个整数n，表示测试题中给出的正整数个数。

第二行有n个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

输入样例

4

1 2 3 4

输出样例

2

说明/提示

【样例说明】

由1+2=3,1+3=4，故满足测试要求的答案为2。

注意，加数和被加数必须是集合中的两个不同的数。

        （1）编程思路。

        为了判断集合中有多少个数恰好等于集合中另外两个（不同的）数之和，定义一个数组int hash[10001]，其中hash[i]=0表示整数i作为和值未出现，hash[i]=1表示整数i作为和值第1次出现了，hash[i]=2表示整数i作为和值不止1次出现了，只能算一次。初始时，hash数组中，属于集合元素的hash数组相应元素值置1，其余非集合元素的相应hash元素值均为0。

         用二重循环

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

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

        对集合中任意两个不同元素的和值t（t=num[i]+num[j]）进行处理。若和值t的对应的hash[t]等于1，表示集合中存在元素t为另外两个不同元素的和，计数，同时置hash[t]=2，以避免下次再出现和值t产生重复计数。

        （2）源程序。

#include <stdio.h>

int main()

{

    int n,i,j,t,cnt=0,num[100];

    int hash[10001]={0};

    scanf("%d",&n);  

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

         {

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

                   hash[num[i]]=1;

         }

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

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

                   {

                            t=num[i]+num[j];

                            if (t<=10000 && hash[t]==1)

                            {       

                                     cnt++;

                                     hash[t]=2;  // 注意：1+4和2+3也算重复，需去掉

                            }

                   }

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

         return 0;

}