河北邯郸网站建设国内cms

河北邯郸网站建设,国内cms,铁路工程建设材料预算价格2网站,凡客诚品倒闭了题目背景要保护环境。题目描述木材厂有 n 根原木#xff0c;现在想把这些木头切割成 k 段长度均为 l 的小段木头#xff08;木头有可能有剩余#xff09;。当然#xff0c;我们希望得到的小段木头越长越好#xff0c;请求出 l 的最大值。木头长度的单位是 cm#xff0c;原…题目背景要保护环境。题目描述木材厂有 n 根原木现在想把这些木头切割成 k 段长度均为 l 的小段木头木头有可能有剩余。当然我们希望得到的小段木头越长越好请求出 l 的最大值。木头长度的单位是 cm原木的长度都是正整数我们要求切割得到的小段木头的长度也是正整数。例如有两根原木长度分别为 11 和 21要求切割成等长的 6 段很明显能切割出来的小段木头长度最长为 5。输入格式第一行是两个正整数 n,k分别表示原木的数量需要得到的小段的数量。接下来 n 行每行一个正整数 Li​表示一根原木的长度。输出格式仅一行即 l 的最大值。如果连 1cm 长的小段都切不出来输出0。输入输出样例输入 #1复制3 7 232 124 456输出 #1复制114说明/提示数据规模与约定对于 100% 的数据有 1≤n≤1051≤k≤1081≤Li​≤108(i∈[1,n])。思路这是一道经典的可以用二分解决的题。我们可以考虑从1到1e8也就是1*10^8题目给的木头最长长度的范围找答案那这么大的数据很明显需要一种思路来优化一下一般的n^2的暴力查找那么就可以想到二分我们可以用l和r做边界l1r1e8用 (rl)/2mid 做二分答案的中间值用while(lr)的循环通过不断调整mid的值用mid值作为可以切割的长度在while循环中开个1到n的for循环让每个完整的木头与mid整除得到符合长度要求的木头用cnt累加。如果cnt当前mid值下可以切割得到满足要求的木头数或者大于那么我们就让lmid1来让长度尽可能的大反之找到满足条件的最大切割长度 。主播的代码:#include iostream #includequeue #includealgorithm #includemap #includevector #includeset #includestack #includestring #includemath.h #include iomanip #includeunordered_map #include unordered_set #includearray #define gets(S) fgets(S,sizeof(S),stdin) #define ll long long const ll N 1e6 5; const ll Max 0x3f3f3f3f; using namespace std; ll n, m; vectorllsaki; ll ef(ll l, ll r) { ll mid 0, cnt 0, ans 0; while (l r) { mid (r l) / 2; for (int i 1; i n; i) { cnt saki[i] / mid; } if (cnt m) { r mid - 1; } else { l mid 1; } cnt 0; } return r; } int main() { cin n m; saki.resize(n 1); for (int i 1; i n; i) { cin saki[i]; } ll l 1, r 1e8; cout ef(l, r) endl; return 0; }