傳送門

木材加工

題目背景

要保護(hù)環(huán)境

題目描述

木材廠有一些原木，現(xiàn)在想把這些木頭切割成一些長(zhǎng)度相同的小段木頭(木頭有可能有剩余)，需要得到的小段的數(shù)目是給定的。當(dāng)然，我們希望得到的小段木頭越長(zhǎng)越好，你的任務(wù)是計(jì)算能夠得到的小段木頭的最大長(zhǎng)度。木頭長(zhǎng)度的單位是cm。原木的長(zhǎng)度都是正整數(shù)，我們要求切割得到的小段木頭的長(zhǎng)度也是正整數(shù)。

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

輸入輸出格式

輸入格式

第一行是兩個(gè)正整數(shù)N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的數(shù)目，K是需要得到的小段的數(shù)目。

接下來(lái)的N行，每行有一個(gè)1到100000000之間的正整數(shù)，表示一根原木的長(zhǎng)度。

輸出格式

能夠切割得到的小段的最大長(zhǎng)度。如果連1cm長(zhǎng)的小段都切不出來(lái)，輸出"0"。

輸入輸出樣例

輸入樣例 #1

3 7 232 124 456

輸出樣例 #1

114

分析

二分答案基礎(chǔ)好題。

思路非常簡(jiǎn)單，二分切出的小段長(zhǎng)度即可。

二分的左邊界l顯然是0，那么右邊界呢？是最短的木棍嗎？

我們來(lái)看這樣一組數(shù)據(jù)

3 6 11 21 1

如果我們把右邊界r定為最短的木棍1，顯然得不到最優(yōu)解。最優(yōu)解根本就不會(huì)用到長(zhǎng)度為1的木棍，所以r定這個(gè)是不行的。

我們不必拘泥于最短的木棍，因?yàn)槟竟骺梢匀拥簟Ｋ晕覀兛梢园裷大膽的定到一個(gè)位置，使得這個(gè)位置是有可能有解的，但是再+1就沒(méi)解的值。

我猜你一定想到了，沒(méi)錯(cuò)，就是把所有木棍的長(zhǎng)度加起來(lái)/k。解最高只能是這個(gè)值了，再高就不行了，因?yàn)槟銢](méi)有那么多原木。

邊界定了，再來(lái)看看check函數(shù)。

check函數(shù)其實(shí)也十分簡(jiǎn)單，模擬一下就行，通過(guò)截取的長(zhǎng)度算出需要多少段，再看看切出的段數(shù)能不能到k。代碼如下：

bool check(int l) {int res = 0;for (int i = 1; i <= n; ++i)res += a[i] / l;//每一根木棍可以截出多少段return res >= k; }

到這里，我們就可以拿80分了，事實(shí)上我們還有一種情況沒(méi)有判斷：一根木棍都截不下來(lái)。這種情況下得到的r是0，mid就會(huì)是0，而check函數(shù)中涉及到了除以mid的操作(mid相當(dāng)于函數(shù)中的l)，所以你懂得。。

所以我們要來(lái)個(gè)特判，如果sum / k < 1，說(shuō)明根本截不下來(lái)，這個(gè)時(shí)候直接輸出0，結(jié)束程序。這樣就可拿到滿分啦。

代碼走起。

代碼

/** @Author: crab-in-the-northeast * @Date: 2020-06-16 01:01:11 * @Last Modified by: crab-in-the-northeast* @Last Modified time: 2020-06-16 01:06:58*/ #include <iostream> #include <cstdio>const int maxn = 100005; int n, k; int a[maxn];bool check(int l) {int res = 0;for (int i = 1; i <= n; ++i)res += a[i] / l;return res >= k; }int main() {std :: cin >> n >> k;int l = 0, r = 0, sum = 0;for (int i = 1; i <= n; ++i) {std :: cin >> a[i];sum += a[i];}if (sum / k < 1) {std :: cout << 0 << std :: endl;return 0;}r = sum / k;while (l <= r) {int mid = l + r >> 1;if (check(mid)) l = mid + 1;else r = mid - 1;}std :: cout << l - 1 << std :: endl;return 0; }

評(píng)測(cè)記錄

評(píng)測(cè)記錄

總結(jié)

以上是生活随笔為你收集整理的[luogu p2440] 木材加工的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。