华为OD刷题C卷 - 每日刷题 12（数组连续和，求最多可以派出多少支团队）

1、（数组连续和）：

这段代码是解决“数组连续和”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算给定数组中有多少个连续区间的和大于等于给定值x。

main方法首先读取数组的长度n和阈值x，然后读取数组nums中的元素。接着，调用getResult方法并打印结果。

getResult方法使用前缀和数组preSum来高效地计算连续区间的和。前缀和数组preSum[i]表示数组中前i个元素的和。通过遍历数组并使用双指针技术（在这里是两个索引l和r），代码可以找到所有满足条件的连续区间。当当前区间的和大于等于x时，由于数组中的数都是正整数，可以确定从当前右指针r开始向左直到数组末尾的所有区间的和也都大于等于x。因此，可以将计数器count增加相应的数量，并将左指针l向右移动以继续寻找下一个区间。

2、（求最多可以派出多少支团队）：

这段代码是解决“求最多可以派出多少支团队”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算在给定最低能力值要求下，最多可以组成多少支团队。

main方法首先读取总人数n，然后读取每个人的能力值数组power，最后读取团队要求的最低能力值minPower。接着，调用getResult方法并打印可以派出的团队数量。

getResult方法首先对能力值数组进行升序排序。然后使用双指针技术，从数组的两端开始，先计算能够单独组队的人数（即能力值大于等于minPower的人数）。接着，从左指针l开始，尝试与右指针r配合，形成能力值总和大于等于minPower的团队。如果两个人的能力值之和小于minPower，则左指针l向右移动，寻找下一个可能的团队组合。

package OD223;import java.util.Scanner;/*** @description 数组连续和* @level 6* @score 100*//*** 题目描述* 给定一个含有N个正整数的数组, 求出有多少个连续区间（包括单个正整数）, 它们的和大于等于x。* <p>* 输入描述* 第一行两个整数N x（0 < N <= 100000, 0 <= x <= 10000000)* <p>* 第二行有N个正整数（每个正整数小于等于100)。* <p>* 输出描述* 输出一个整数，表示所求的个数。* <p>* 注意：此题对效率有要求，暴力解法通过率不高，请考虑高效的实现方式。*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//数组个数int n = sc.nextInt();//需要大于等于xint x = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = sc.nextInt();}System.out.println(getResult(nums, x));}//有多少个连续数组和大于等于xpublic static long getResult(int[] nums, int x) {long len = nums.length;long count = 0;//因为有效率要求，不能每次都求和，用前缀和来表示long[] preSum = new long[(int) (len + 1)];//preSum[i]表示前面i个数的和for (int i = 1; i <= len; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];}//while循环int l = 0;int r = 1;while (r <= len) {long sum = preSum[r] - preSum[l];if (sum >= x) {//[l,r]区间的和已经大于x了，则[l,r,....len-1]区间的和必定大于x （都是正整数）count += len - r + 1;//窗口滑动l++;r = l + 1;} else {r++;}}return count;}}

package OD226;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** @description 求最多可以派出多少支团队* @level 5* @score 100*//*** 题目描述* 用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或者2人组成，且1个人只能参加1个团队，计算出最多可以派出多少只符合要求的团队。* <p>* 输入描述* 第一行代表总人数，范围1-500000* 第二行数组代表每个人的能力* 数组大小，范围1-500000* 元素取值，范围1-500000* 第三行数值为团队要求的最低能力值，范围1-500000* 输出描述* 最多可以派出的团队数量*/
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//代表总人数int n = sc.nextInt();//每个人的能力值int[] power = new int[n];for (int i = 0; i < n; i++) {power[i] = sc.nextInt();}//团队要求最低能力值int minPower = sc.nextInt();System.out.println(getResult(power, minPower));}//最多可以派出多少团队 能一个人满足的就一个人组队public static int getResult(int[] power, int minPower) {int n = power.length;//升序排列Arrays.sort(power);//双指针int l = 0;int r = n - 1;int count = 0;//先记录单人组队while (r >= l && power[r] >= minPower) {count++;r--;}//把小于<=minPower的两两分组 尽可能多while (l < r) {int sum = power[l] + power[r];//如果此时无法组队，则l位置的不可能组队成功if (sum < minPower) {l++;} else {//组队成功count++;l++;r--;}}return count;}
}