例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×105），表示數字個數，
第二行 n 個正整數表示ai （1≤ai ≤109），
輸出格式
僅一行一個整數表示答案，
若若取模結果去重后剩余數字不足兩個，則輸出 ?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×105）的范圍較大，因此像樣例解釋的那樣，采用二重回圈將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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412843.html
標籤：C