洛谷P3817 Java解法
程序员文章站
2022-06-13 13:20:09
...
题目出处点这里
思路:不断遍历相邻两个数i、i+1并取他们的和neighborSum,如果和大于x,就要吃掉tempSum=neighborSum-x个糖果,先吃第i+1个盒子里的,如果arr[i+1]>=tempSum就从arr[i+1]里减去tempSum个即可,如果arr[i+1]<tempSum,就把arr[i+1]吃光置为0,再去吃前一个的即可。如此循环i-1遍即可,最后把每个需要吃掉的糖果数tempSum相加即可。
代码如下:
package greedy;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
public class P3817 {
static long sum = 0;
static int tempSum;// 用来存储临时的吃掉的糖果数
static int[] arr;
static int neighborSum;// 相邻两个数的和
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n - 1; i++) {
neighborSum = arr[i] + arr[i + 1];
if (neighborSum > x) {
tempSum = neighborSum - x;// 相邻两个糖果数的和减去x就是要吃掉的糖果数
if (arr[i + 1] >= tempSum) {//当arr[i+1]大于等于要吃掉的糖果数的时候
arr[i + 1] = arr[i + 1] - tempSum;//直接在第i+1个糖果盒里吃就行
} else {//如果arr[i+1]小于要吃掉的糖果数,那么可以先把arr[i+1]=0(也就是把第i+1个糖果盒的全吃完),再去arr[i]里吃就行
arr[i+1] = 0;
//其实不加这一句也行,因为tempSum已经记录下来且我们是向后遍历,我们只需要改变arr[i+1]即可
// arr[i] = arr[i] - (tempSum - arr[i+1]);
}
sum = sum + tempSum;
}
}
System.out.println(sum);
}
}
上一篇: linux(centos)中的cron计划任务配置方法[详细]
下一篇: P3817 小A的糖果