每日OJ题_牛客_比那名居的桃子_滑动窗口/前缀和_C++_Java

目录

牛客_比那名居的桃子_滑动窗口/前缀和

题目解析

C++代码

Java代码

---

牛客_比那名居的桃子_滑动窗口/前缀和

比那名居的桃子 (nowcoder.com)

描述：

        小红有一天看到了一只桃子，由于桃子看上去就很好吃，小红很想把它吃掉。
已知吃下桃子后，每天可以获得 ai​ 的快乐值，但是每天会获得 bi​ 的羞耻度。桃子的持续效果一共为 k 天。

小红想知道，自己在哪一天吃下果实，可以获得尽可能多的快乐值？

        如果有多个答案获得的快乐值相等，小红希望获得尽可能少的羞耻度。如果有多个答案的快乐值和羞耻度都相等，由于小红实在太想吃桃子了，她希望尽可能早的吃下桃子。

---

题目解析

• 滑动窗口的思想： 由题意要枚举所有大小为 k 的子数组，并且求出这段子数组中快乐值和羞耻度之和。因此可以利用滑动窗口的思想，用两个变量维护大小为 k 的窗口的总和，并且不断更新即可。
• 前缀和思想： 这个就比较简单了，先预处理出来快乐值和羞耻度的前缀和数组，然后枚举的过程中直接求出一段区间的和即可。但是相比较于滑动窗口的思想，会有空间消耗。

C++代码

#include <climits>
#include <ios>
#include <iostream>
#include <vector>
using namespace std;
#define int long longsigned main()
{int n = 0, k = 0; // k是滑动窗口的大小cin >> n >> k;vector<int> a(n), b(n);for (int i = 0; i < n; ++i){cin >> a[i];}for (int i = 0; i < n; ++i){cin >> b[i];}int aSum = 0, bSum = 0, res = 0;int aMax = INT_MIN, bMin = INT_MAX;for (int left = 0, right = 0; right < n; ++right){aSum += a[right]; // 进窗口bSum += b[right]; // 进窗口while(right - left + 1 > k) // 判断{aSum -= a[left];bSum -= b[left];++left; // 出窗口}if(aSum > aMax || (aSum == aMax && bSum < bMin)) // 更新结果{res = left;aMax = aSum;bMin = bSum;}}cout << res + 1 << endl;return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt(), 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);}
}