笔试强训-day17_T3 比那名居的桃子

本文主要是介绍笔试强训-day17_T3 比那名居的桃子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目链接
比那名居的桃子

二、题目描述
小红有一天看到了一只桃子，由于桃子看上去就很好吃，小红很想把它吃掉。
已知吃下桃子后，每天可以获得 𝑎_𝑖的快乐值，但是每天会获得b_𝑖的羞耻度。桃子的持续效果一共为 𝑘天。小红想知道，自己在哪一天吃下果实，可以获得尽可能多的快乐值？
如果有多个答案获得的快乐值相等，小红希望获得尽可能少的羞耻度。
如果有多个答案的快乐值和羞耻度都相等，由于小红实在太想吃桃子了，她希望尽可能早的吃下桃子。
输入描述:

输出描述:

三、答案解析

算法思路
①暴力解法
②滑动窗⼝的思想：
由题意得，我们是要枚举所有⼤⼩为 k 的⼦数组，并且求出这段⼦数组中快乐值和羞耻度之和。因
此，可以利⽤滑动窗⼝的思想，⽤两个变量维护⼤⼩为 k 的窗⼝的总和，并且不断更新即可。
③前缀和思想：
这个就⽐较简单了，先预处理出来快乐值和羞耻度的前缀和数组，然后枚举的过程中直接求出⼀段
区间的和即可。但是相⽐较于滑动窗⼝的思想，会有空间消耗。

代码解答

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();long[] a = new long[n + 1];long[] b = new long[n + 1];for (int i = 1; i <= n; i++) {a[i] = in.nextLong();}for (int i = 1; i <= n; i++) {b[i] = in.nextLong();}int left = 1, right = 1;long hSum = 0, sSum = 0, hMax = 0, sMin = 0, begin = 0;while (right <= n) {//进窗口hSum += a[right];sSum += b[right];//出窗口while (right - left + 1 > k) {hSum -= a[left];sSum -= b[left];left++;}//更新结果if (right - left + 1 == k) {if (hSum > hMax) {begin = left;hMax = hSum;sMin = sSum;} else if (hSum == hMax && sSum < sMin) {begin = left;sMin = sSum;}}right++;}System.out.println(begin);}   
}

本题使用滑动窗口解答，另外两种方法大家可以自己试一试，对于暴力解法可能会出现超时，但是使用前缀和的方法应该是可以的。

这篇关于笔试强训-day17_T3 比那名居的桃子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---