木材加工 解題報告

$\mathrm{D}\mathrm{e}\mathrm{s}\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{p}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

描述

木材廠有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有剩余），需要得到的小段的數目是給定的。當然，我們希望得到的小段木頭越長越好，你的任務是計算能夠得到的小段木頭的最大長度。木頭長度的單位是$cm$。原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數。

例如有兩根原木長度分別為$11$和$21$，要求切割成到等長的$6$段，很明顯能切割出來的小段木頭長度最長為$5$.

輸入

第一行是兩個正整數$N$和$K$$(1\le N\le 100000，1\le K\le 100000000)$，$N$是原木的數目，$K$是需要得到的小段的數目。

接下來的$N$行，每行有一個$1$到$100000000$之間的正整數，表示一根原木的長度。

輸出

能夠切割得到的小段的最大長度。如果連$1cm$長的小段都切不出來，輸出$“0”$。

輸入樣例

3 7
232
124
456

輸出樣例

114

解題部分

思路

二分切割的長度，用這個長度去切木頭，看看可以切多少段，當段數小于數目時，就說明切的長度太長，需要縮小，則把 $\mathrm{r}$ 賦值為$\mathrm{m}\mathrm{i}\mathrm{d}$，同理，當段數大于數目時，就說明切的長度太短，需要放大，則把 $\mathrm{l}$ 賦值為$\mathrm{m}\mathrm{i}\mathrm{d}$。

int l=0,r=100000;//細節，如果這里l設為1，那么當切不了的時候，就會輸出1。所以要用0。 while(l+1 < r) {ans=0;//細節：計數器要歸零。int mid=(l+r)/2;for(int i=1; i<=n; i++)ans+=a[i]/mid;//累加能切的段數if (ans>=k)l=mid;else if (ans<k)r=mid; }

提交代碼地址
提交代碼地址(有改動)
注：在做第二道題時，可以把繩子擴大100倍再進行二分答案。記得看好許局類型，什么時候用double,什么時候用int。

總結

以上是生活随笔為你收集整理的木材加工 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。