华为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_Xif (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]部分，返回trueint j = i + 1;//高一位不够，则再高一位，不能超过minuend.lengthwhile (j < minuend.length) {//如果能借，则-1，返回trueif (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;}}