C语言程序设计100例之(48):钢管加工


例48  钢管加工

问题描述

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

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

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

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

输入格式

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

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

输出格式

加工的最短时间。

输入样例

5 6 3

5 4 3 2 1

输出样例

样例解释

第一秒塞入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

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×105),表示数字个数。

第二行 n 个正整数表示ai (1≤ai ≤109)。

输出格式

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

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

输入样例

4 5 5 6

输出样例

样例解释

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

去重后有:{0,1,2,4,5},结果为4。

         (1)编程思路。

        由于正整数n(3≤n≤2×105)的范围较大,因此像样例解释的那样,采用二重循环将n个正整数两两的余数求出来,去重后再找到一个次大值的方法会超时的。

        实际上,对于任意的两个不同的正整数a和b,若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

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。

输入样例

14

10

输出样例

说明/提示

样例中,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

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表示必须向右移动的次数。在每个测试用例后打印一个空行。

输入样例

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

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;

}

相关