阿里笔试 7-24，第一题提交不通过？
第一题，吃烧饼
N个盘子，每个盘子上有Si个烧饼
每次选择第x个盘子（x的区间：1-N），将1，2, 3，···x盘子里面的都吃一个，如果其中有一个没有烧饼，x不能选择。
问最多能吃多少？
输入：
3
2 1 3
输出：
4
检查了好几遍没啥问题，一直提交不通过，请各位老铁帮我检查~ ，我的代码如下：
import java.util.Scanner;
public class Main1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int[] arrs = new int[num];
if (num >= 1 && num <= Math.pow(10,6)){
int res = 0;
for (int i = 0; i < num; i++) {
arrs[i] = sc.nextInt();
}
for (int i = num - 1; i >= 0 ; i--) {
if (isExistes(arrs,i)){
res = res + i + 1;
jian(arrs,i);
}
}
if (arrs[0] > 0){
res = res + arrs[0];
}
System.out.println(res);
}
}
public static boolean isExistes(int[] arrs, int n){
for (int i = 0; i <= n; i++) {
if (arrs[i]<=0){
return false;
}
}
return true;
}
public static void jian(int[] arrs, int n){
for (int i = 0; i <= n; i++) {
arrs[i] = arrs[i] - 1;
}
}
}
上面思路错了，经过大佬们的指点，利用动态规划的思想，改正代码如下：
import java.util.Scanner;
public class Cake {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
long[] arrs = new long[num];
long res = 0;
long min = Long.MAX_VALUE;
for (int i = 0; i < num; i++) {
arrs[i] = sc.nextLong();
min = Math.min(arrs[i],min);
res += min;
}
sc.close();
System.out.println(res);
}
}
OPPO公司福利 1202人发布