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;
}