华为OD刷题C卷 - 每日刷题 22（计算面积、绘图机器，信道分配）

1、（计算面积、绘图机器）：

这段代码是解决“计算面积、绘图机器”的问题。它提供了一个Java类Main，其中包含main方法，用于计算绘图机器按照给定指令绘制直线所形成的图形面积。

main方法首先读取指令数量n和横坐标终点值end_X。然后，初始化面积和area为0，以及上一个点的坐标last_X和last_Y。通过循环读取每条绘制指令，包括当前点的横坐标cur_X和纵坐标偏移量offset_Y。对于每条指令，计算当前点与上一个点和x轴围成的图形面积，并更新面积和。

在循环结束后，如果end_X大于上一个点的横坐标last_X，则计算从上一个点到end_X的面积，并将其添加到总面积中。

最后，打印出计算得到的面积。

2、（信道分配）：

这段代码是解决“信道分配”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，以及辅助方法binary_sub和cals_bin，用于计算最多可以为多少用户传输数据。

main方法首先读取信道的最大阶数R，每种信道的数量N数组，以及单个用户需要传输的数据量D。然后，调用getResult方法并打印最多可以服务的用户数量。

getResult方法首先将D转换为逆序的二进制表示，并初始化一个用户数量计数器count。然后，对于大于D的二进制位数的信道，直接将它们的数量加到count中。

接着，使用binary_sub方法进行二进制减法，模拟信道分配过程。只要结果大于0，就表示可以再满足一个用户的数据传输需求。binary_sub方法实现了二进制减法的逻辑，包括处理借位和欠债的情况。

cals_bin方法用于计算一个二进制数组表示的十进制数值，用于在binary_sub方法中计算信道的总容量。

最后，getResult方法返回满足数据传输需求的用户数量。

package OD320;

import java.util.Scanner;

/**
 * @description 计算面积、绘图机器
 * @level 6
 * @score 100
 */

/**
 * 题目描述
 * 绘图机器的绘图笔初始位置在原点(0,0)机器启动后按照以下规则来进行绘制直线。
 * <p>
 * 尝试沿着横线坐标正向绘制直线直到给定的终点E
 * 期间可以通过指令在纵坐标轴方向进行偏移，offsetY为正数表示正向偏移,为负数表示负向偏移
 * 给定的横坐标终点值E 以及若干条绘制指令，
 * <p>
 * 请计算绘制的直线和横坐标轴以及x=E的直线组成的图形面积。
 * <p>
 * 输入描述
 * 首行为两个整数 N 和 E
 * <p>
 * 表示有N条指令,机器运行的横坐标终点值E
 * <p>
 * 接下来N行 每行两个整数表示一条绘制指令x offsetY
 * <p>
 * 用例保证横坐标x以递增排序的方式出现
 * <p>
 * 且不会出现相同横坐标x
 * <p>
 * 取值范围
 * <p>
 * 0<N<=10000
 * 0<=x<=E<=20000
 * -10000<=offsetY<=10000
 * 输出描述
 * 一个整数表示计算得到的面积 用例保证结果范围在0到4294967295之内。
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //n条指令
        int n = sc.nextInt();
        //横坐标终点值
        int end_X = sc.nextInt();
        //面积和
        int area = 0;
        //上一个点的坐标
        int last_X = 0;
        int last_Y = 0;
        for (int i = 0; i < n; i++) {
            //当前点的x坐标
            int cur_X = sc.nextInt();
            //当前点在y轴上的偏移量
            int offset_Y = sc.nextInt();
            //把该点与上一个点与x轴围成的面积算出来 不分正负
            area += (cur_X - last_X) * Math.abs(last_Y);

            //更新上一个点的坐标
            last_X = cur_X;
            last_Y = last_Y + offset_Y;
        }
        //因为要保证沿着x正向划线，所以前面的点坐标不可能超过end_X
        if (end_X > last_X) {
            area += (end_X - last_X) * Math.abs(last_Y);
        }
        System.out.println(area);
    }
}

package OD334;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @description 信道分配
 * @level 9
 * @score 200
 * @url https://hydro.ac/d/HWOD2023/p/OD334
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //信道的最大阶数
        int R = sc.nextInt();

        //0-R阶信道的个数
        int[] N = new int[R + 1];
        for (int i = 0; i <= R; i++) {
            N[i] = sc.nextInt();
        }

        //单个传输需要的数据量
        int D = sc.nextInt();

        //输出最多可以供多少用户传输数据
        System.out.println(getResult(R, N, D));

    }

    public static int getResult(int R, int[] N, int D) {
        //将D转为二进制并逆序 如30 -> 二进制：11110 -> 逆序：01111 N[]=[10,5,0,1,3,2]
        //表示需要花费对应信道的个数，其中N[5]对应的1个就可以满足一个用户
        int[] subtrahend = Arrays.stream(new StringBuilder(Integer.toBinaryString(D)).reverse().toString().split(""))
                .mapToInt(Integer::parseInt).toArray();

        //能满足的用户数量
        int count = 0;

        //大于subtrahend的信道数量,一个就可以满足一个用户
        for (int i = R; i >= subtrahend.length; i--) {
            count += N[i];
        }

        //剩余的信道数量，去掉大于subtrahend的信道数量，位数相同[0,subtrahend.length)
        int[] minuend = Arrays.copyOfRange(N, 0, subtrahend.length);

        //进行二进制减法，只要结果大于0，则说明可以再满足一个用户
        while (binary_sub(minuend, subtrahend)) {
            count++;
        }

        return count;

    }

    /**
     * minuend[]剩余信道个数，是否还能承载一个subtrahend[]
     *
     * @param minuend
     * @param subtrahend
     * @return boolean
     */
    public static boolean binary_sub(int[] minuend, int[] subtrahend) {
        //减法逻辑，从高位开始
        for (int i = minuend.length - 1; i >= 0; i--) {
            //如果对应位置的信道足够，直接相减
            if (minuend[i] >= subtrahend[i]) {
                minuend[i] -= subtrahend[i];
            } else {
                //不够，则要么向高位借1，要么向低位欠2
                //需要看minuend的[0,i]部分能承载的信道是否大于subtrahend的[0,i]部分，如果不能，只能向高位借
                if (cals_bin(Arrays.copyOfRange(minuend, 0, i + 1)) < cals_bin(Arrays.copyOfRange(subtrahend, 0, i + 1))) {
                    //向高位借 只要能借到一个，就能承载[0,i]部分，返回true
                    int j = i + 1;
                    //高一位不够，则再高一位，不能超过minuend.length
                    while (j < minuend.length) {
                        //如果能借，则-1，返回true
                        if (minuend[j] > 0) {
                            minuend[j]--;
                            return true;
                        } else {
                            //j位不够借，到j+1位借
                            j++;
                        }
                    }
                    //j一直借到最高位都没有借的，则剩下部分不足以再分配给一个用户了
                    return false;
                } else {
                    //低位能承载 minuend[i]<subtrahend[i] 向低位借
                    //此时minuend[i]为负数，表示欠债
                    minuend[i] -= subtrahend[i];

                    //将欠债加到低位，低位需要承担双倍
                    minuend[i - 1] += minuend[i] * 2;

                    //i位置的欠债清空
                    minuend[i] = 0;
                }
            }
        }
        //默认结果大于0，表示可以承载一个用户
        return true;
    }

    /**
     * 返回bin[]信道能承载的信道总数
     *
     * @param bin
     * @return int
     */
    public static int cals_bin(int[] bin) {
        int ans = 0;
        for (int i = 0; i < bin.length; i++) {
            ans += (int) (bin[i] * Math.pow(2, i));
        }
        return ans;
    }


}