題目背景

要保護環境

題目描述

木材廠有?�n?根原木，現在想把這些木頭切割成?�k?段長度均為?�l?的小段木頭（木頭有可能有剩余）。

當然，我們希望得到的小段木頭越長越好，請求出?�l?的最大值。

木頭長度的單位是?cmcm，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數。

例如有兩根原木長度分別為?1111?和?2121，要求切割成等長的?66?段，很明顯能切割出來的小段木頭長度最長為?55。

輸入格式

第一行是兩個正整數?�,�n,k，分別表示原木的數量，需要得到的小段的數量。

接下來?�n?行，每行一個正整數?��Li?，表示一根原木的長度。

輸出格式

僅一行，即?�l?的最大值。

如果連?1cm1cm?長的小段都切不出來，輸出?0。

輸入輸出樣例

輸入 #1復制

3 7
232
124
456

輸出 #1復制

114

說明/提示

數據規模與約定

對于?100%100%?的數據，有?1≤�≤1051≤n≤105，1≤�≤1081≤k≤108，1≤��≤108(�∈[1,�])1≤Li?≤108(i∈[1,n])。

額，隨便寫寫吧。

這是一道二分查找的題，題目很簡單，簡單套用一下二分查找的模版就可以輕松ac了。

代碼：

#include<bits/stdc++.h>
using namespace std;int n,k,a[100005],longest,l=1,mid,sum;
int main(){cin>>n>>k;for(int i=0;i<n;i++){cin>>a[i];longest=max(longest,a[i]);}while(l<=longest){mid=(l+longest)/2;sum=0;for(int i=0;i<n;i++){sum+=a[i]/mid;}if(sum>=k)l=mid+1;else longest=mid-1;}cout<<longest;return 0;
}