牛客对应题目链接：比那名居的桃子 (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 来存变量。
