蓝桥杯第17届省赛A组真题-切割木材-二分查找-排序

解题思路:本题目就是在区间范围为[1,1000000000]范围内找到一个最小的target，使得题目的条件成立。而不难找到L越宽时，需要的K的次数越小，L越窄时，需要的K的次数越多，很容易想到L与K之间有递减关系，再联想寻找最小的合适值target，使用二分查找解决问题。

注意事项:

要注意数组的边界、upper_bound函数的寻找机制、mid的是否为0。

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

int N,K,A[1000005],l,r,mid;

bool judge()

{

if(mid>=A[N]) return true;

if(mid==0) return false; 

int pos = upper_bound(A+1, A+N+1,mid) - A, count=0;

for(int i = pos;i <= N; i++)

{

count+=A[i]/mid;

if(mid!=0&&A[i]%mid == 0) count--;

}

return count <= K;

}

int main()

{

scanf("%d%d",&N,&K);

for(int i = 1; i <= N; i++)

{

scanf("%d",A+i);

}

sort(A+1,A+N+1);

l = 0, r = 1e9*2;

while(l < r)

{

mid = (l+r)>>1;

if(judge()) r = mid;

else l = mid+1;

}

printf("%d\n",l);

return 0;

}