例48  钢管加工

问题描述

有N根钢管，每根长度是ai，有一个钢管加工器，每秒钟可以加工k长度的钢管，工人师傅需要按顺序加工这些钢管，

不过呢，机器的最大等待长度是h，即等待加工（已经塞入机器却还没有加工的钢管）的钢管长度不能超过h（保证ai <= h)，

加工工人只能在整数秒的时候塞入钢管，

求加工完这些钢管最少要多久，

输入格式

第一行N、H、K，代表钢管条数，最大等待长度和每秒处理速度，

接下来N行，每行一个数，代表钢管的长度，这些钢管需要按顺序处理，

输出格式

加工的最短时间，

输入样例

5 6 3

5 4 3 2 1

输出样例

5

样例解释：

第一秒塞入5，等待长度5，机器处理了3，等待长度2

第二秒塞入4，等待长度6，机器处理了3，等待长度3

第三秒塞入3，等待长度6，机器处理了3，等待长度3

第四秒塞入了1,2，等待长度6，机器处理了3，等待长度3

第五秒无塞入，等待长度3，机器处理了3，处理完毕

          （1）编程思路，

        定义变量len保存上次加工后剩余的等待加工的钢管长度，初始值为0，定义变量ans保存最短的总加工时间，初始值也为0，

        依次输入待加工的钢管长度a，若len+a>h，待加工的钢管不能塞入加工器，先等待机器加工处理之前剩余的待处理钢管，此时ans加1，之前剩余的处理后，剩余的没有了，新的钢管作为待加工的钢管len=a；若len+a<=h，将待加工钢管塞入加工处理器，一块加工处理，每次加工处理，加工时间加上机器最大处理的时间（即ans+=len/k），加工处理后，剩余长度len=len%k一定小于机器一秒处理的长度k，

        所有钢管依次读入处理后，若最后len不为0，再花1秒去处理剩余的，即ans++，

         （2）源程序，

#include <stdio.h>

int main()

{

    int n,h,k;

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

    long long ans=0;

    int i;

    int a,len=0;

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

    {

        scanf("%d",&a);

        if (len+a>h)

        {

            ans++;

            len=a;

        }

        else

            len+=a;

        ans+=len/k;

        len%=k;

    }

    if (len!=0) ans++;

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

    return 0;

}

习题48

48-1   次大值

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

问题描述

Alice 有 n 个正整数，数字从1～n 编号，分别为a1 ,a2,…,an，

Bob 刚学习取模运算，于是便拿这n 个数进行练习，他写下了所有

ai mod aj  (1≤i,j≤n∧i≠j)的值，其中mod 表示取模运算，

Alice 想知道所有的结果中，严格次大值是多少，将取模后得到的所有值进行去重，即相同的结果数值只保留一个，剩余数中第二大的值就称为严格次大值，

输入格式

第一行一个正整数n（3≤n≤2×10⁵），表示数字个数，

第二行 n 个正整数表示ai （1≤ai ≤10⁹），

输出格式

仅一行一个整数表示答案，

若若取模结果去重后剩余数字不足两个，则输出 ?1，

输入样例

4

4 5 5 6

输出样例

4

样例解释

所有取模的结果为{4,4,4,1,0,5,1,0,5,2,1,1}，

去重后有：{0,1,2,4,5}，结果为4，

         （1）编程思路，

        由于正整数n（3≤n≤2×10⁵）的范围较大，因此像样例解释的那样，采用二重回圈将n个正整数两两的余数求出来，去重后再找到一个次大值的方法会超时的，

        实际上，对于任意的两个不同的正整数a和b，若a<b，则a mod b的值一定为a，而b mod a的值为0~a-1之一，小于a，

        因此，在n个正整数中，若最大正整数为max1，次大的正整数为max2（且max2不等于max1），则在这n个正整数的两两求余所得的余数中，最大的余数一定为max2，

        严格次大的余数为多少呢？

        设n个正整数中，第3大的正整数为max3（且max3与max1和max2均不相等），则任意比max3小的正整数x与最大整数max1产生的余数（最大可能为x）一定也小于max3，因此，严格次大的余数不可能由比max3小的正整数求余得到，

        Max3是不是次大的正整数呢？还需比较一下max3与max1 mod max2的值，例如，三个正整数2、4、15，显然最大余数为4，次大的为15 mod 4（值为3），不是2，

        因此，本题可这样解决，求出输入的n个正整数的最大值max1、次大值max2和第3大值max3，可以一边输入资料一边求值（max1、max2和max3的初始值均设为0），

        n个资料输入完成后，若max3不等于0，则次大值为max3和max1%max2的较大值；若max3等于0且max2不等于0，则序列中只有两个不同的正整数max1和max2，最大的余数为max2，次大的余数一定为max1%max2；若max2等于0，则序列中的n个资料全部相同，余数去重后只剩下1个，没有次大余数，输出-1，

        （2）源程序，

#include <stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    int max1=0,max2=0,max3=0;

    int i,x;

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

    {

        scanf("%d",&x);

        if (x==max1 || x==max2 || x==max3) continue;

        if (x>max1)

        {

            max3=max2;  max2=max1; max1=x;

        }

        else

        {

             if (x>max2)

             {

                 max3=max2;  max2=x;

             }

             else if (x>max3) max3=x;

        }

    }

    if (max3!=0) printf("%d\n",max3>max1%max2?max3:max1%max2);

    else if (max2!=0) printf("%d\n",max1%max2);

    else printf("-1\n");

    return 0;

}

48-2  和能被7整除

问题描述

设有N个整数构成的序列a[1]，a[2]，…，a[n]，求一个最长的区间[x，y]，使得区间中的数a[x]，a[x+1]，a[x+2]，…，a[y-1]，a[y]的和能被7整除，输出区间长度，若没有符合要求的区间，输出0，

输入格式

输入的第一行是整数N（1≤N≤50,000)，之后N行，每行给出序列中的整数值a[i] （范围为0~1,000,000），

输出格式

输出区间长度，若没有符合要求的区间，输出0，

输入样例

7

3

5

1

6

2

14

10

输出样例

5

说明/提示

样例中，5+1+6+2+14 = 28符合要求，最大长度为5，.

         （1）编程思路，

        定义阵列int left[7]={0,-1,-1,-1,-1,-1,-1},right[7]={0};分别保存当前累加和整除7后的余数第1次和最后一次出现的位置，

        以样例中3、5、1、6、2、14、10的7个数为例，依次累加7个数得到的累加和为3、8、9、15、17、31、41，除以7的余数分别为3、1、2、1、3、3、6，由此得到left[3]=1，right[3]=6，即从第2个（left[3]+1）数到第6个（right[3]）数的累加和一定是7的倍数，区间长度为5（6-2+1），Left[1]=2，right[1]=4，即从第3个（left[1]+1）数到第4个（right[1]）数的累加和也一定是7的倍数，但这个区间只有2个数，比余数为3取得的区间短，

        因此，可根据累加和求得各相同余数的第一次和最后一次之间的位置，再列举0~6 共7个余数各自的最长长度，在它们7个中找出最长的就是所求，

        （2）源程序，

#include <stdio.h>

int main()

{

    int n;

    scanf("%d",&n);

    int left[7]={0,-1,-1,-1,-1,-1,-1},right[7]={0};

    int i,a;

    int sum=0;

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

    {

        scanf("%d",&a);

        sum=(sum+a)%7;

        if (left[sum]==-1) left[sum]=i;

        right[sum]=i;

    }

    int ans=0;

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

        if (right[i]-left[i]>ans) ans=right[i]-left[i];

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

    return 0;

}

48-3  向左和向右

问题描述

某二叉树中的每个结点都包含一对整数，树的结构如下所示：

根包含整数对（1，1），

如果结点包含整数对（a，b），则其左子结点包含整数对（a+b，b），其右子结点包含整数对（a，a+b），

给定上述二叉树的某个结点的所包含的整数对（a，b），假设您沿着最短路径从树的根走到给定结点，你能知道走动程序中你向左移动多少次，向右移动多少次吗？

输入

第1行给出测验资料的组数，

每组测验资料都由一行组成，其中包含两个整数a和b（1<=a，b<=2*109），表示结点（a，b），您可以假设这是上述二叉树中的有效结点，

输出

每组测验资料的输出都以一行开头，其中包含“Scenario #i:”，其中i是从1开始的测验用例编号，然后打印一行，其中包含两个数字l和r，两个数字之间用一个空格隔开，其中l表示从根到输入中给定的结点遍历树时必须向左移动的次数，r表示必须向右移动的次数，在每个测验用例后打印一个空行，

输入样例

3

42 1

3 4

17 73

输出样例

Scenario #1:

41 0

 

Scenario #2:

2 1

 

Scenario #3:

4 6

 

          （1）编程思路，

        定义变量int lcnt=0，rcnt=0；分别保存向左转和向右转的次数，

        从终结点（a，b）开始逆推，若a比b大的话，肯定是由结点（a-b,b）向左走过来的，此时lcnt++，a=a-b；若a比b小的话，肯定是由结点（a,b-a）向左走过来的，此时rcnt++，b=b-a，这样逆推直到根结点，此时a=1且b=1，

        在逆推程序中，可能连续向左或连续向右，为了加速处理，可以用除法代替减法，从而减少回圈次数，具体代码参见源程序，

        （2）源程序，

#include <stdio.h>

int main()

{

    int n;

       scanf("%d",&n);

       int i;

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

       {

              int a,b;

              scanf("%d%d",&a,&b);

              int lcnt=0,rcnt=0,t;

              while (a>1 || b>1)

              {

                     if (a>b)

                     {

                            t=(a-1)/b;

                            lcnt+=t;

                            a-=t*b;

                     }

                     else

                     {

                            t=(b-1)/a;

                            rcnt+=t;

                            b-=t*a;

                     }

              }

              printf("Scenario #%d:\n",i);

              printf("%d %d\n\n",lcnt,rcnt);

       }

    return 0;

}