欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P3817 Java解法

程序员文章站 2022-06-13 13:20:09
...

题目出处点这里
洛谷P3817 Java解法思路:不断遍历相邻两个数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);
	}
}