題解 | #比那名居的桃子3種解法#
比那名居的桃子
https://ac.nowcoder.com/acm/problem/224679
// 暴力解法
#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; // 記錄這一段區(qū)間的和
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;
}
// 滑動(dòng)窗口
#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)
{
// 進(jìn)窗口
sumHpy+=a[right]; sumSme+=b[right];
// 進(jìn)多了->出窗口
while(right-left+1>k)
{
sumHpy-=a[left];
sumSme-=b[left++];
}
// 判斷&&更新結(jié)果
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;
// 輸入數(shù)據(jù)+維護(hù)前綴和數(shù)組
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;
}