Weekly Contest 363 - 三题哥+1

Q1. Sum of Values at Indices With K Set Bits

暴力模拟即可

1. class Solution {
   
2.     public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
   
3.         int sum = 0;
   
4.         for (int i = 0; i < nums.size(); i++) {
   
5.             int cnt = 0;
   
6.             int temp = i;
   
7.             while (temp > 0) {
   
8.                 if (temp % 2 != 0) cnt++;
   
9.                 temp >>= 1;
   
10.             }
    
11.             if (cnt == k) sum += nums.get(i);
    
12.         }
    
13.         return sum;
    
14.     }
    
15. }

复制代码

Q2.  Happy Students

不难证明，选x个学生的方案有且仅有一种。所以sort之后直接便利即可。

1. class Solution {
   
2.     public int countWays(List<Integer> nums) {
   
3.         int n = nums.size();
   
4.         Collections.sort(nums);
   
5.         int ret = 0;
   
6.         if (nums.get(0) > 0) ret ++;
   
7.         if (nums.get(n - 1) < n) ret ++;
   
8.         for (int i = 1; i < n; i++) {
   
9.             int left = nums.get(i - 1);
   
10.             int right = nums.get(i);
    
11.             if (i > left && i <  right) ret++;
    
12.         }
    
13.         return ret;      
    
14.     }
    
15. }

复制代码

Q3.Maximum Number of Alloys

每一个机器有个最优解，对所有机器取max


每一个机器通过二分搜索拿到最优解，注意这里二分又边界是21e8, 一开始写的1e8发现hidden case过不了。这里2*1e8是因为 budget和 库存 最大值为1e8，两个相加。

1. class Solution {
   
2.     public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
   
3.         int max = 0;
   
4.         for (List<Integer> compo : composition) {
   
5.             max = Math.max(max, helper(n, k, budget, stock, compo, cost));
   
6.         }
   
7.         return max;
   
8.         
   
9.     }
   
10.    
    
11.     private int helper(int n, int k, int budget, List<Integer> stock, List<Integer> compo, List<Integer> cost) {
    
12.         int remain = budget;
    
13.         int left = 0, right = (int)(2 * 1e8);
    
14.         while (left + 1 < right) {
    
15.             int mid = left + (right - left) / 2;
    
16.             if (ok(mid, budget, compo, stock, cost)) left = mid;
    
17.             else right = mid;
    
18.         }
    
19.         
    
20.         if (ok(right, budget, compo, stock, cost)) return right;
    
21.         if (ok(left, budget, compo, stock, cost)) return left;
    
22.         return -1;
    
23.     }
    
24.    
    
25.     private boolean ok(int target, int budget, List<Integer> compo, List<Integer> stock, List<Integer> cost) {
    
26.         long demand = 0L;
    
27.         if (target == 0) return true;
    
28. 
    
29.         for (int i = 0; i < compo.size(); i++) {
    
30.             demand += (long)compo.get(i) * cost.get(i);
    
31.         }
    
32.         
    
33.         long total = demand * target;
    
34.         for (int i = 0; i < stock.size(); i++) {
    
35.             if (stock.get(i) >= (long)target * compo.get(i)) total -= (long)cost.get(i) * target * compo.get(i);
    
36.             else total -= (long)cost.get(i) * stock.get(i);
    
37.         }
    
38.         return total <= budget;
    
39.     }
    
40. }

复制代码