华为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)机器启动后按照以下规则来进行绘制直线。
 * 

 * 尝试沿着横线坐标正向绘制直线直到给定的终点E
 * 期间可以通过指令在纵坐标轴方向进行偏移，offsetY为正数表示正向偏移,为负数表示负向偏移
 * 给定的横坐标终点值E 以及若干条绘制指令，
 * 

 * 请计算绘制的直线和横坐标轴以及x=E的直线组成的图形面积。
 * 

 * 输入描述
 * 首行为两个整数 N 和 E
 * 

 * 表示有N条指令,机器运行的横坐标终点值E
 * 

 * 接下来N行 每行两个整数表示一条绘制指令x offsetY
 * 

 * 用例保证横坐标x以递增排序的方式出现
 * 

 * 且不会出现相同横坐标x
 * 

 * 取值范围
 * 

 * 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;
}
}