本文主要是介绍洛谷 P2440 木材加工(二分答案),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
思路:和跳石头那道题基本上一模一样,都是二分答案的类型,找到答案的左边界(0)和右边界(最长的那一个木头),套二分模板即可,具体可以见http://t.csdnimg.cn/Af1fa
#include<stdio.h>
#define s 100010
int arr[s];
int n, k;
int judge(int mid)
{int i = 1, count = 0;while(i <= n) //从第i根木头一直到第n根木头{int len = arr[i]; //长度赋值count += len / mid; //这一根木头能切的段数++i; //下一根木头}if (count >= k) //如果切出来的段数比要求的多或者相等,说明mid有可能小了或者相等{return 1;}else //如果切出来的段数比要求的少,说明mid大了{return 0;}
}
int main()
{int max = 0;scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) //输入木头的长度{scanf("%d", &arr[i]);if (arr[i] > max){max = arr[i]; }}int left = 0, right = max + 1; //找到二分答案的左边界和右边界while (left + 1 != right) //二分答案排除{int mid = (left + right) / 2;if (judge(mid)) //短了{left = mid;}else //长了{right = mid;}}if (judge(right)) //因为right比left大,所以right如果符合题意,就选right{printf("%d\n", right);}else //right不符合题意,那就是left{printf("%d\n", left);}return 0;
}
这篇关于洛谷 P2440 木材加工(二分答案)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!