题解 | #比那名居的桃子3种解法#

// 暴力解法
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll n, k, a[N], b[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)    cin>>a[i];
    for(int i=1;i<=n;++i)    cin>>b[i];
    
    ll ans=0, maxHpy=LONG_MIN, minSme=LONG_MAX;
    for(int i=1;i<=n;++i)
    {
        ll sumHpy=0, sumSme=0;    // 记录这一段区间的和
        for(int j=i, cnt=1;j<=n&&cnt<=k;++j, ++cnt)
        {
            sumHpy+=a[j];
            sumSme+=b[j];
        }
        if(sumHpy>maxHpy)
        {
            maxHpy=sumHpy;
            minSme=sumSme;
            ans=i;
        }
        if(sumHpy==maxHpy)
        {
            if(sumSme<minSme)
            {
                minSme=sumSme;
                ans=i;
            }
        }
    }
    cout<<ans;
    return 0;
}

// 滑动窗口
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll n, k, a[N], b[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)    cin>>a[i];
    for(int i=1;i<=n;++i)    cin>>b[i];
    
    ll ans=1, maxHpy=LONG_MIN, minSme=LONG_MAX, sumHpy=0, sumSme=0;
    for(int left=1, right=1;right<=n;++right)
    {
        // 进窗口
        sumHpy+=a[right]; sumSme+=b[right];
         // 进多了->出窗口
        while(right-left+1>k)
        {
            sumHpy-=a[left];
            sumSme-=b[left++];
        }
        // 判断&&更新结果
        if(right-left+1==k)
        {
            if(sumHpy>maxHpy)
            {
                maxHpy=sumHpy;
                minSme=sumSme;
                ans=left;
            }
            else if(sumHpy==maxHpy)
            {
                if(sumSme<minSme)
                {
                    minSme=sumSme;
                    ans=left;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

// 前缀和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
using ll = long long;
ll n, k, a[N], b[N], prefixA[N], prefixB[N];
int main()
{
    cin>>n>>k;
    // 输入数据+维护前缀和数组
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        prefixA[i]=prefixA[i-1]+a[i];
    }
    for(int i=1;i<=n;++i)
    {
        cin>>b[i];
        prefixB[i]=prefixB[i-1]+b[i];
    }
    ll ans=1, maxHpy=LONG_MIN, minSme=LONG_MAX, sumHpy=0, sumSme=0;
    for(int i=1;i<=n;++i)
    {
        if(i+k-1<=n)
        {
            sumHpy = prefixA[i+k-1]-prefixA[i-1];
            sumSme = prefixB[i+k-1]-prefixB[i-1];
            if(sumHpy>maxHpy)
            {
                maxHpy=sumHpy;
                minSme=sumSme;
                ans=i;
            }
            else if(sumHpy==maxHpy)
            {
                if(sumSme<minSme)
                {
                    minSme=sumSme;
                    ans=i;
                }
            }
        }
    }
    cout<<ans;
    
    return 0;
}