d164 - 七、最佳选择
題目描述
題目要求在環形排列的 N 頭奶牛中，選出連續的 M 頭奶牛，使得選出的奶牛的品質數總和最大。
解題思路
本題可以使用滑動視窗的概念來解決。由於奶牛是環形排列的，因此需要考慮滑動視窗跨越環的邊界的情況。程式碼中，外層迴圈遍歷每一頭奶牛作為滑動視窗的起始點，內層迴圈計算從該起始點開始的 M 頭奶牛的品質數總和。如果起始點加上 M 大於 N，則表示滑動視窗跨越了環的邊界，需要將環的後半部分加到總和中。在計算每一組 M 頭奶牛的總和後，更新最大總和。
複雜度分析
- 時間複雜度: O(N*M)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
int a[10000];
int s[10000];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int N,M;
while(cin >> N >> M){
int max=0;
for(int i=0;i<N;i++){
cin >> a[i];
s[i]=0;
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++)
(i+j>=N)?s[i]+=a[i+j-N]:s[i]+=a[i+j];
if(s[i]>max)
max=s[i];
}
cout << max << '\n';
}
}