做房产网站需要了解什么,百度云建网站,自己做服务器的网站,网站两边广告代码链接#xff1a;
2560. 打家劫舍 IV
题意
n个数字#xff0c;相邻不能选#xff0c;选择的结果为 选中的数字中的最大数字#xff0c;要求最少选k个数字
求这个结果最小能是多少
解#xff1a;
怎么就从DP变成二分了呢#xff1f;
关键字#xff1a;最大的最小
…链接
2560. 打家劫舍 IV
题意
n个数字相邻不能选选择的结果为 选中的数字中的最大数字要求最少选k个数字
求这个结果最小能是多少
解
怎么就从DP变成二分了呢
关键字最大的最小
最少选k个数字又要结果最小那尽量少选且使选中的最大数字最小则题目变成选择k个数字使选中的数字中最大的数字最小(选的越少选取条件越宽松则理论上能取的数字越小
二分答案Check逻辑贪心能选的就选上只要满足小于等于temp_ans就先选上选够了k个说明这个temp_ans合法
实际代码
#includebits/stdc.h
using namespace std;
bool check(vectorint nums,int limit, int k)
{int xz0;for(int i0;inums.size();i){if(nums[i]limit){xz;if(xzk) return true;i;}}return false;
}
int minCapability(vectorint nums, int k)
{int l0,r0;for(auto num:nums) rmax(r,num);while(lr){int midl(r-l)1;coutmidendl;if(check(nums,mid,k)){lmid;}else rmid-1;}return l;
}限制
1 nums.length 1051 nums[i] 1091 k (nums.length 1)/2
