房地产交易网站模版,wordpress订阅地址,wordpress前段会员中心,营销型网站如何制作1. 题意
给定一个数组#xff0c;和一个最多次操作次数。每次操作可以将数组中的一个数 x x x分成两个数 t x − t t\quad x-t tx−t。问 m a x O p e r a t i o n C n t maxOperationCnt maxOperationCnt次操作后#xff0c;数组中最大的数最小的值是多少。
2. 题解
这个…1. 题意
给定一个数组和一个最多次操作次数。每次操作可以将数组中的一个数 x x x分成两个数 t x − t t\quad x-t tx−t。问 m a x O p e r a t i o n C n t maxOperationCnt maxOperationCnt次操作后数组中最大的数最小的值是多少。
2. 题解
这个题我们需要转换思路不要去想怎么分而是经过操作后数组中有几个数。对于一个数 x x x要使它分割后小于 y y y, 我们肯定分割后尽量都分成每个数都为 y y y, 因此最后的堆数为 ⌈ x y ⌉ \lceil \frac{x}{y}\rceil ⌈yx⌉, 分割的次数为 ⌊ x − 1 y ⌋ \lfloor\frac{x-1}{y}\rfloor ⌊yx−1⌋。
再将数组排好序数进行二分每次尝试数 x x x看需要的分割数 s p l i t C n t splitCnt splitCnt是否小于等于 m a x O p e r a t i o n C n t maxOperationCnt maxOperationCnt s p l i t C n t ∑ x i ∈ S ⌊ x i − 1 y ⌋ S : { x i , x i y } splitCnt\sum_{x_i\in S}\lfloor\frac{x_i-1}{y}\rfloor\quad \\S :\{x_i,x_i y\} splitCntxi∈S∑⌊yxi−1⌋S:{xi,xiy}
代码一
class Solution {
public:int logcnt(int base,int v) {int ans 0;while (base v) {v (v 1)/2;ans;}return ans;}bool check(const vectorint nums, int val,int bid, int maxCnt) {int sz nums.size();int ndcnt 0;for (int i bid;i sz;i) {ndcnt (nums[i] - 1) / val;}return ndcnt maxCnt;}int FindNotLess(const vectorint a, int v) {int l 0;int r a.size();while (l r) {int mid (l r) 1;if (a[mid] v)l mid 1;else r mid - 1;}return l;}int minimumSize(vectorint nums, int maxOperations) {sort(nums.begin(), nums.end());int sz nums.size();int l 1;int r *nums.rbegin();while (l r) {int val (l r) 1;// int idx FindNotLess(nums, val);vectorint::iterator it upper_bound(nums.begin(), nums.end(), val);int ndCnt 0;// for (int i idx;i sz;i) {// ndCnt (nums[i] - 1) / val;// }for (;it ! nums.end(); it) {ndCnt ((*it) - 1)/val;}if (ndCnt maxOperations) {r val;}else {l val 1;}}return l;}
};其实不需要排序的直接尝试遍历整个数组就好了
03xf的代码
class Solution {
public:int minimumSize(vectorint nums, int maxOperations) {auto check [](int m) - bool {long long cnt 0;for (int x : nums) {cnt (x - 1) / m;}return cnt maxOperations;};int left 0; // 循环不变量 check(left) falseint right ranges::max(nums); // 循环不变量 check(right) truewhile (left 1 right) {int mid left (right - left) / 2;(check(mid) ? right : left) mid;}return right;}
};
参考
03xf
