lcp363

100031. 计算 K 置位下标对应元素的和

方法一：模拟

class Solution {
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int n = nums.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            int x = Integer.bitCount(i);
            if (x == k)
                res += nums.get(i);
        }
        return res;
    }
}

100040. 让所有学生保持开心的分组方法数

方法一：排序 + 贪心

判断起初和结束位置：即全不选和全选

class Solution {
    public int countWays(List<Integer> nums) {
        int n = nums.size(), res = 0;
        Collections.sort(nums);
        int cnt = 0;
        if (nums.get(0) != 0)
            res++;
        for (int i = 0; i < n - 1; ++i) {
            ++cnt;
            int x = nums.get(i), y = nums.get(i + 1);
            if (cnt > x && cnt < y)
                ++res;
        }
        ++cnt;
        if (cnt > nums.get(n - 1))
            ++res;
        return res;
    }
}

100033. 最大合金数

方法一：二分查找

以后二分r都用1e18！！！

class Solution {
        public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
            long res = 0;
            for (List<Integer> comp : composition) {
                long l = 0, r = Integer.MAX_VALUE;
                while (l <= r) {
                    long mid = (l + r) >> 1;
                    if (check(mid, n, budget, comp, stock, cost))
                        l = mid + 1;
                    else
                        r = mid - 1;
                }
                res = Math.max(res, r);
            }
            return (int) res;
        }

        private boolean check(long cnt, int n, long budget, List<Integer> comp, List<Integer> stock,List<Integer> cost) {
            long[] requires = new long[n];
            for (int i = 0; i < n; ++i) {
                requires[i] = Math.max(comp.get(i) * cnt - stock.get(i), 0);
                budget -= requires[i] * cost.get(i);
            }
            return budget >= 0;
        }

}