每日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 long

signed 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);
    }
}