提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

0005 ALGO1003-礼物

2023-04-18 15:37:48 时间

问题描述

试题 算法训练 礼物
image

原始解法（暴力超时）

最简单也最容易想到保证超时，bushi的就是暴力解法：从头遍历到尾部，每次检验可以带走的石头数量，可带走更多则更新。不出意外的超时了，就过了俩 case。

import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.14 12:28:36
 * @description [试题 算法训练 礼物](http://lx.lanqiao.cn/problem.page?gpid=T2990)
 */

public class A1003_Present {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 数据输入
			int src_n = sc.nextInt();
			long src_s = sc.nextLong();
			int[] src = new int[src_n];
			for (int i=0; i<src_n; ++i) {
				src[i] = sc.nextInt();
			}
			
			// 数据处理
			int res = solve(src, src_s);
			
			// 结果输出
			System.out.println(res);
		}
	}
	
	/**
	 * 暴力解法，从头遍历到尾部，每次检验可以带走的石头数量，可带走更多则更新
	 * @param stones 石头重量数组
	 * @param S 最大的石头重量
	 * @return 可以带走的最大石头数量
	 */
	public static int solve(int[] stones, long S) {
		int num = 0;
		for (int i=0; i+num<stones.length; ++i) {
			long s = S;
			int n = 0;
			// 从当前石头出发，最多可以带走多少石头（结果为 n 个）
			// j + n < length 
			// 代表若从当前出发，带走 n 个 石头后，若剩余不足 n 个石头则不用继续增加
			for (int j=i; j+n<stones.length; ++j) {
				s -= stones[j];
				if (s >= 0) {
					++n;
				} else {
					break;
				}
			}
			// 判断后 n 个石头的重量
			s = 0;
			int rear = i + (n << 1);
			for (int j=i+n; j<rear; ++j) {
				s += stones[j];
			}
			// 若后 n 个石头重量大于可以携带的重量
			while (s > S) {
				s = s + stones[i + (--n)]; // 前移曾加 1 个
				s -= stones[--rear] + stones[--rear]; // 前移丢掉 2 个 
			}
			if (rear - i > num) { // 若当前可携带量大于已有的最优结果，则更新
				num = rear - i;
			}
		}
		return num;
	}
	
}

改进解法（内存超限）

一番Ctrl C V思考之后，暴力解法存在很多重复计算，时间复杂度来到 (O(KN))，(K) 指的是可能带走的石头数量，(N) 则是石头总量。借鉴大佬的想法，添加一个数组（假设为 area），用以保存从 (i) 出发可以选择的石头数量。然后判断从 (i) 出发，由 num 至 i + area[i] 范围内是否存在可以带走 j - i 个石头（(j in (num, i + area[i]])）
更详细的描述见：蓝桥杯 试题 算法训练 礼物 C++ 详解

爆内存的代码如下（最多过了 5 个 case，最少也是过了俩）

import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.14 12:28:36
 * @description [试题 算法训练 礼物](http://lx.lanqiao.cn/problem.page?gpid=T2990)
 */

public class A1003_Present {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 数据输入
			int src_n = sc.nextInt();
			long src_s = sc.nextLong();
			int[] src = new int[src_n];
			for (int i=0; i<src_n; ++i) {
				src[i] = sc.nextInt();
			}
			
			// 数据处理
			long sum = 0;
			int num = 0;
			int i, j;
			for (i=0; i<src_n; ++i) { // 从 i 出发，获取可选的石头范围
				while (sum<src_s && num<src_n) { // 获取当前可选的重量
					sum += src[num++];
				}
				if (sum > src_s) { // 超重，抛掉最后一个石头
					sum -= src[--num];
				}
				if (num < i) { // 此时可选的数量小于出发点
					sum = 0; // 总重量置 0
					src[i] = 0; // 从 i 出发不能带走任何石头
					num = i + 1; // 置于下一个出发点
				} else {
					sum -= src[i]; // 抛掉当前石头
					src[i] = num - i;// 可选石头的数量
				}
			}
			
			int res = 0;
			for (i=0; i<src_n; ++i) {
				for (j=src[i]; j>res; --j) { // 可选范围比已知最大范围要大
					// 后 j 个石头没越界，且后 j 个石头重量要小于等于 S
					if (i+j<src_n && src[i + j]>=j) {
						res = j;
						break;
					}
				}
			}
			res <<= 1;
			
			// 结果输出
			System.out.println(res);
		}
	}
}

AC 解法

然后又是一番搜索，发现有老哥说 Scanner 性能太拉，又是一番 Ctrl C V，修正如下：
此处参考：

  1. 蓝桥杯算法训练 礼物 java (不使用二分查找)
    这个佬好像用的新解法，没仔细看。
  2. 为什么内存超限了，求高手解答（附代码）
    image
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.14 12:28:36
 * @description [试题 算法训练 礼物](http://lx.lanqiao.cn/problem.page?gpid=T2990)
 */

public class A1003_Present {
	
	private static int[] src;
	private static int src_n;
	private static long src_s;

	public static void main(String[] args) throws IOException {
		// 数据输入
//		try (Scanner sc = new Scanner(System.in)) {
//			src_n = sc.nextInt();
//			src_s = sc.nextLong();
//			src = new int[src_n];
//			for (int i = 0; i < src_n; ++i) {
//				src[i] = sc.nextInt();
//			}
//		}
		
		try (InputStreamReader isr = new InputStreamReader(System.in)) {
			try (BufferedReader br = new BufferedReader(isr)) {
				String[] tmp = br.readLine().split(" ");
				src_n = Integer.parseInt(tmp[0]);
				src_s = Long.parseLong(tmp[1]);
				
				src = new int[src_n];
				tmp = br.readLine().split(" ");
				for (int i=0; i<src_n; ++i) {
					src[i] = Integer.parseInt(tmp[i]);
				}
			}
		}
		
		// 数据处理
		// 结果输出
		System.out.println(solve1());
	}

	/**
	 * 解法 1：暴力解法（超时，只能过 2 个 case）
	 * 	从头遍历到尾部，每次检验可以带走的石头数量，可带走更多则更新
	 * @return 可以带走的最大石头数量
	 */
	public static int solve() {
		int num = 0;
		for (int i = 0; i + num < src.length; ++i) {
			long s = src_s;
			int n = 0;
			// 从当前石头出发，最多可以带走多少石头（结果为 n 个）
			// j + n < length
			// 代表若从当前出发，带走 n 个 石头后，若剩余不足 n 个石头则不用继续增加
			for (int j = i; j + n < src.length; ++j) {
				s -= src[j];
				if (s >= 0) {
					++n;
				} else {
					break;
				}
			}
			// 判断后 n 个石头的重量
			s = 0;
			int rear = i + (n << 1);
			for (int j = i + n; j < rear; ++j) {
				s += src[j];
			}
			// 若后 n 个石头重量大于可以携带的重量
			while (s > src_s) {
				s = s + src[i + (--n)]; // 前移曾加 1 个
				s -= src[--rear] + src[--rear]; // 前移丢掉 2 个
			}
			if (rear - i > num) { // 若当前可携带量大于已有的最优结果，则更新
				num = rear - i;
			}
		}
		return num;
	}

	/**
	 * 解法 2：空间换时间
	 *  解法 1 中有大量重复的计算，使用一个表示可选区域大小的数组降低计算量
	 * 参考：https://blog.csdn.net/Lyz_ID/article/details/122906021
	 * @return 可以带走的最大石头数量
	 */
	public static int solve1() {
		int i, j;
		int num = 0;
		long sum = 0;
		
		for (i=0; i<src_n; ++i) { // 从 i 出发，获取可选的石头范围
			while (sum<src_s && num<src_n) { // 获取当前可选的重量
				sum += src[num++];
			}
			if (sum > src_s) { // 超重，抛掉最后一个石头
				sum -= src[--num];
			}
			if (num < i) { // 此时可选的数量小于出发点
				sum = 0; // 总重量置 0
				src[i] = 0; // 从 i 出发不能带走任何石头
				num = i + 1; // 置于下一个出发点
			} else {
				sum -= src[i]; // 抛掉当前石头
				src[i] = num - i;// 可选石头的数量
			}
		}

		num = 0;
		for (i=0; i<src_n; ++i) {
			for (j=src[i]; j>num; --j) { // 可选范围比已知最大范围要大
				// 后 j 个石头没越界，且后 j 个石头重量要小于等于 S
				if (i+j<src_n && src[i+j]>=j) {
					num = j;
					break;
				}
			}
		}
		return (num << 1);
	}

}

AC 贴图：
image

时间复杂度约为 (O(n))。
总结：Java 基础太差，还是要好好学 Java。
再次感谢各位佬的无私分享~

相关文章