【算法题】信道分配

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 标题：信道分配 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
 * 算法工程师小明面对着这样一个问题，需要将通信用的信道分配给尽量多的用户：
 * 信道的条件及分配规则如下：
 * 1) 所有信道都有属性：”阶”。阶为r的信道的容量为2^r比特；
 * 2) 所有用户需要传输的数据量都一样：D比特；
 * 3) 一个用户可以分配多个信道，但每个信道只能分配给一个用户；
 * 4) 只有当分配给一个用户的所有信道的容量和>=D，用户才能传输数据；
 * 给出一组信道资源，最多可以为多少用户传输数据？
 * 输入描述:
 * 第一行，一个数字R。R为最大阶数。
 * 0<=R<20
 * 第二行，R+1个数字，用空格隔开。 代表每种信道的数量Ni。按照阶的值从小到大排列。
 * 0<=i<=R, 0<=Ni<1000.
 * 第三行，一个数字D。 D为单个用户需要传输的数据量。
 * 0<D<1000000
 * 输出描述:
 * 一个数字，代表最多可以供多少用户传输数据。
 * 示例1
 * 输入
 * 5
 * 10 5 0 1 3 2
 * 30
 * 输出
 * 4
 * 说明
 * 最大阶数为5.
 * 信道阶数： 0  1  2  3   4   5
 * 信道容量： 1  2  4  8  16  32
 * 信道个数：10  5  0  1   3   2
 * 单个用户需要传输的数据量为30
 * 可能存在很多分配方式，举例说明：
 * 分配方式1：
 * 1) 32*1 = 32
 * 2) 32*1 = 32
 * 3) 16*2 = 32
 * 4) 16*1 + 8*1 + 2*3 = 30
 * 剩下2*2 + 1*10=14不足以再分一个用户了。
 * 分配方式2：
 * 1) 16*1 + 8*1 + 2*3 = 30
 * 2) 16*1 + 2*2 + 1*10 = 30
 * 3) 32*1 = 32
 * 4) 32*1 = 32
 * 剩下16*1=16不足以再分一个用户了。
 * 分配方式3：
 * 1) 16*1 + 8*1 + 2*3 = 30
 * 2) 16*1 + 2*2 + 1*10 = 30
 * 3) 16*1 + 32*1 = 48
 * 4) 32*1 = 32
 * 恰好用完。
 * 虽然每种分配方式剩下的容量不同，但服务的用户数量是一致的。因为这个问题中我们只关心服务的用户数，所以我们认为这些分配方式等效。
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int R = sc.nextInt();
        int[] cnt = new int[R + 1];
        for (int i = 0; i <= R; i++) {
            cnt[i] = sc.nextInt();
        }
        int D = sc.nextInt();
        sc.close();

        int users = 0;
        while (allocateOneUser(cnt, D, R)) {
            users++;
        }
        System.out.println(users);
    }

    // 尝试为单个用户分配信道，成功返回 true 并直接修改 cnt 数组
    private static boolean allocateOneUser(int[] cnt, int D, int R) {
        int need = D;
        // 优先使用容量不超过当前需求的信道，从大到小避免浪费
        for (int i = R; i >= 0; i--) {
            if (cnt[i] > 0 && (1 << i) <= need) {
                int take = Math.min(cnt[i], need / (1 << i));
                cnt[i] -= take;
                need -= take * (1 << i);
            }
        }
        if (need == 0) return true;
        // 若用小信道无法凑够，则使用一个容量大于剩余需求的最小信道
        for (int i = 0; i <= R; i++) {
            if (cnt[i] > 0 && (1 << i) > need) {
                cnt[i]--;
                return true;
            }
        }
        return false;
    }
}