比那名居的桃子题解_前缀和算法

原题：https://ac.nowcoder.com/acm/contest/11214/D

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct momo{
    ll hapy,sham;
    int dy;
}mm[100010],sum[100010],day[100010];
bool cmp(momo x,momo y){
    if(x.hapy==y.hapy) return x.sham<y.sham;
    else return x.hapy>y.hapy;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>mm[i].hapy;
    for(int i=1;i<=n;i++) cin>>mm[i].sham;
    sum[0].hapy=0;sum[0].sham=0;
    for(int i=1;i<=n;i++)
        sum[i].hapy=sum[i-1].hapy+mm[i].hapy;
    for(int i=1;i<=n;i++)
        sum[i].sham=sum[i-1].sham+mm[i].sham;
    for(int i=1;i<=n-k+1;i++){
        day[i].dy=i;
        day[i].hapy=sum[i+k-1].hapy-sum[i-1].hapy;//前缀和
        day[i].sham=sum[i+k-1].sham-sum[i-1].sham;
    }
    sort(day+1,day+1+n-k+1,cmp);
    cout<<day[1].dy<<endl;
    return 0;
}