0005 ALGO1003-禮物
問題描述
原始解法（暴力超時）
最簡單也最容易想到保證超時，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，修正如下：
此處參考：
- 藍橋杯算法訓練 禮物 java (不使用二分查找)
這個佬好像用的新解法，沒仔細看。 - 為什么內存超限了，求高手解答（附代碼）
![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 貼圖：
時間復雜度約為 \(O(n)\)。
總結：Java 基礎太差，還是要好好學 Java。
再次感謝各位佬的無私分享~
浙公網安備 33010602011771號