【错题集-编程题】比那名居的桃子（滑动窗口 / 前缀和）-阿里云开发者社区

【错题集-编程题】比那名居的桃子（滑动窗口 / 前缀和）

2024-05-22 22

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【错题集-编程题】比那名居的桃子（滑动窗口 / 前缀和）

牛客对应题目链接：比那名居的桃子 (nowcoder.com)

一、分析题目

1、滑动窗口

由题意得，我们是要枚举所有大小为 k 的子数组，并且求出这段⼦数组中快乐值和羞耻度之和。因此，可以利用滑动窗口的思想，用两个变量维护大小为 k 的窗口的总和，并且不断更新即可。

2、前缀和

这个就比较简单了，先预处理出来快乐值和羞耻度的前缀和数组，然后枚举的过程中直接求出⼀段区间的和即可（sum[i+k-1] - sum[i-1]）。但是相比较于滑动窗口的思想，会有空间消耗。

二、代码

1、看题解之前AC的代码

//滑动窗口
#include <iostream>
using namespace std;
 
typedef long long LL;
const int N=1e5+10, INF=1e9+7;
int happy[N], shame[N];
 
int main()
{
    LL n, k;
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> happy[i];
    for(int i=0; i<n; i++) cin >> shame[i];
    int left=0, right=0;
    LL sum_happy=0, sum_shame=0;
    LL max_happy=0, min_shame=INF;
    LL st=0;
    while(right<n)
    {
        sum_happy+=happy[right];
        sum_shame+=shame[right];
        while(right-left+1>k)
        {
            sum_happy-=happy[left];
            sum_shame-=shame[left];
            left++;
        }
        if(right-left+1==k)
        {
            if(sum_happy>=max_happy)
            {
                if(sum_happy==max_happy && sum_shame<min_shame)
                {
                    st=left;
                    max_happy=sum_happy;
                    min_shame=sum_shame;
                }
                else if(sum_happy>max_happy)
                {
                    st=left;
                    max_happy=sum_happy;
                    min_shame=sum_shame;
                }
            }
        }
        right++;
    }
    cout << st+1 << endl; 
    return 0;
}

2、看了题解之后AC的代码

//前缀和
#include <iostream>
using namespace std;
 
typedef long long LL;
const int N=1e5+10, INF=1e9+7;
int happy[N], shame[N];
LL preHappy[N], preShame[N]; 
 
int main()
{
    LL n, k;
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> happy[i];
    for(int i=1; i<=n; i++) cin >> shame[i];
    for(int i=1; i<=n; i++)
    {
        preHappy[i]=preHappy[i-1]+happy[i];
        preShame[i]=preShame[i-1]+shame[i];
    }
    LL max_happy=0, min_shame=INF;
    int st=0;
    for(int i=1; i<=n-k+1; i++)
    {
        LL sum_happy=preHappy[i+k-1]-preHappy[i-1];
        LL sum_shame=preShame[i+k-1]-preShame[i-1];
        if(sum_happy==max_happy && sum_shame<min_shame)
        {
            st=i;
            max_happy=sum_happy;
            min_shame=sum_shame;
        }
        else if(sum_happy>max_happy)
        {
            st=i;
            max_happy=sum_happy;
            min_shame=sum_shame;
        }
    }
    cout << st << endl;
    return 0;
}

3、值得学习的代码

// 滑动窗⼝
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
LL n, k;
LL h[N], s[N];
 
int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> s[i];
 
    LL left = 0, right = 0;
    LL hSum = 0, sSum = 0, hMax = 0, sMin = 0, begin = 0;
 
    while(right <= n)
    {
        hSum += h[right];
        sSum += s[right];
        while(right - left + 1 > k)
        {
            hSum -= h[left];
            sSum -= s[left];
            left++;
        }
        if(right - left + 1 == k)
        {
            if(hSum > hMax)
            {
                begin = left;
                hMax = hSum;
                sMin = sSum;
            }
            else if(hSum == hMax && sSum < sMin)
            {
                begin = left;
                hMax = hSum;
                sMin = sSum;
            }
        }
        right++;
    }
 
    cout << begin << endl;
 
    return 0;
}

三、反思与改进

像这种设计题目背景的，一定要结合用例将题意弄清楚，否则思路很有可能是错的。虽然没有想到前缀和的方法，但想到了滑动窗口。因为数据量的原因，这里得用 long long 来存变量。