leetcode_1760 袋子里最少数目的球

1. 题意

给定一个数组，和一个最多次操作次数。每次操作可以将数组中的一个数$x$分成两个数$tx-t$。问$maxOperationCnt$次操作后，数组中最大的数最小的值是多少。

2. 题解

这个题，我们需要转换思路，不要去想怎么分，而是经过操作后数组中有几个数。对于一个数$x$，要使它分割后小于$y$, 我们肯定分割后尽量都分成每个数都为$y$, 因此最后的堆数为$\lceil \frac{x}{y}\rceil$, 分割的次数为$\lfloor \frac{x-1}{y}\rfloor$。

再将数组排好序数，进行二分，每次尝试数$x$，看需要的分割数$splitCnt$是否小于等于$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\} splitCnt=xi​∈S∑​⌊yxi​−1​⌋S:={xi​,xi​>y}

• 代码一

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 vector<int> &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 vector<int> &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(vector<int>& 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);vector<int>::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(vector<int>& 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