例34   最长连号

题目描述

输入n个正整数,(1<=n<=10000),要求输出最长的连号的长度。(连号指从小到大连续自然数)

输入格式

第一行,一个数n;

第二行,n个正整数,之间用空格隔开。

输出格式

一个数,最长连号的个数。

输入样例

10

3 5 6 2 3 4 5 6 8 9

输出样例

5

        (1)编程思路。

        依次读入n个数,每读入下一个数x1,总与前一个数x0进行比较,若x1==x0+1,是连号,连号个数cnt++;若x1!=x0+1,不是连号,若当前求得的cnt最大,更新最长连号个数max,重新置cnt=1(x1作为新序列第1个数)。

        由于输入的全部为正整数,因此,初始时可置前一个数x0=0,cnt=0。程序写成一个简单的循环。

        (2)源程序。

#include <stdio.h>

int main()

{

    int n,x0,x1,cnt,max;

    scanf("%d",&n);

    cnt=0,max=0,x0=0;

    while (n--)

    {

       scanf("%d",&x1);

       if (x1==x0+1)

          cnt++;

       else

        {

            if (cnt>max)  max=cnt;

            cnt=1;

        }

        x0=x1;

    }

    printf("%dn",max);

       return 0;

}

习题34

34-1  统计天数

      本题选自洛谷题库 (https://www.luogu.org/problem/P1567)

题目描述

炎热的夏日,KC 非常的不爽。他宁可忍受北极的寒冷,也不愿忍受厦门的夏天。最近,他开始研究天气的变化。他希望用研究的结果预测未来的天气。

经历千辛万苦,他收集了连续 N (1≤N≤106 ) 的最高气温数据。

现在,他想知道最高气温一直上升的最长连续天数。

输入格式

第 1 行:一个整数 N 。1≤N≤106

第 2 行:N个空格隔开的整数,表示连续 N 天的最高气温。0≤ 最高气温≤109  。

输出格式

1 行:一个整数,表示最高气温一直上升的最长连续天数。

输入样例

10

1 2 3 2 4 5 6 8 5 9

输出样例

5

       (1)编程思路。

        同例34的解法。依次读入n个数,每读入下一个数x1,总与前一个数x0进行比较,若x1>x0,气温上升,连续上升天数cnt++;若x1<=x0,气温不是上升的,若当前求得的cnt最大,更新最长连续天数max,重新置cnt=1(x1作为新序列第1个温度)。

        由于输入的数据>=0,因此,初始时可置前一个数x0=0,cnt=0。程序写成一个简单的循环。

      (2)源程序。

#include <stdio.h>

int main()

{

    int n,x0,x1,cnt,max;

    scanf("%d",&n);

    cnt=0,max=0,x0=0;

    while (n--)

    {

       scanf("%d",&x1);

       if (x1>x0)

          cnt++;

       else

        {

            if (cnt>max)  max=cnt;

            cnt=1;

        }

        x0=x1;

    }

    printf("%dn",max);

       return 0;

}

34-2  低洼地  

        本题选自洛谷题库 (https://www.luogu.org/problem/P1317)

题目描述

一组数,分别表示地平线的高度变化。高度值为整数,相邻高度用直线连接。找出并统计有多少个可能积水的低洼地?

 

如图:地高变化为 0 1 0 2 1 2 0 0 2 0

输入格式

两行,第一行n,表示有n个数。第2行连续n个数表示地平线高度变化的数据,保证首尾为0。(3<=n<=10000,0<=高度<=1000)

输出格式

一个数,可能积水低洼地的数目。

输入样例

10

0 1 0 2 1 2 0 0 2 0

输出样例

3

       (1)编程思路。

        由图示可以看出,一个低洼地一定是左边是下坡,右边是上坡。设输入的前后两个数分别为pre和next,若next<pre,一定形成下坡,可置标志down=1;若next>pre,此时是上坡,若前面的下坡已形成(即down=1),则一定形成低洼地,cnt++,同时置down=0。

        用一个简单的循环读入N个数,读入下一个数按上述办法与前一个数比较并进行相应处理即可。

      (2)源程序。

#include<stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    int pre,next,ans=0,down=0;

    scanf("%d",&pre);

    for (int i=2;i<=n;i++)

    {

        scanf("%d",&next);

        if (next<pre) down=1;

        if (next>pre && down==1) { ans++;  down=0;}

        pre=next;

    }

    printf("%dn",ans);

    return 0;

}

34-3  山路爬升

        本题选自洛谷题库 (https://www.luogu.com.cn/problem/P6489)

题目描述

Tomislav 去爬山。他所走的山路可以看做一个长度为n 的数字序列 Pi,Pi表示位置i 的高度为Pi。

从低处往高处走一段连续的高度严格递增的山路称为一次爬升。

为了锻炼身体,他想走一段落差尽量大的爬升。

一段山路的落差定义为这段山路的结束点与起始点的差。

你需要求出他走一段山路所能达到最大的落差是多少。

输入格式

输入第一行一个整数n,表示山路的长度。

第二行n 个整数Pi,表示位置 ii 的高度为Pi。

输出格式

输出一行一个整数,表示最大的落差。

如果整条山路不包含任何的爬升,则输出 0。

输入样例 #1

5

1 2 1 4 6

输出样例 #1

5

输入样例 #2

8

12 20 1 3 4 4 11 1

输出样例 #2

8

输入样例 #3

6

10 8 8 6 4 3

输出样例 #3

0

      (1)编程思路。

        先读入高度P1作为pre,记爬升高度sum和最大爬升高度ans均为0。之后依次读入n-1个高度,每读入下一个高度cur,总与前一个高度pre进行比较,若cur>pre,向上爬升,修改爬升高度sum=sum+(cur-pre),若修改后的sum>ans,置ans=sum;若cur<=pre,不是爬升,更新爬升高度sum=0。程序写成一个简单的循环。

     (2)源程序。

#include<stdio.h>

int main()

{

   int n;

   scanf("%d",&n);

   int ans=0;

   int pre,cur;

   scanf("%d",&pre);

   int sum=0;

   for (int i=2;i<=n;i++)

   {

       scanf("%d",&cur);

       if (cur>pre)

       {

           sum=sum+cur-pre;

           if (sum>ans) ans=sum;

       }

       else

          sum=0;

       pre=cur;

   }

   printf("%dn",ans);

   return 0;

}

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/cs-whut/p/15248649.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!

相关课程