Mr. Z's cows are arranged in a circle in a circular corridor, with each cow marked with an integer between 0 and 255, representing the cow's "quality number"—the higher the number, the better the quality. To showcase his cleverness, Mr. Z has made an unusual agreement with the buyer: the buyer can only select `M` consecutive cows from the corridor. As a smart buyer, you naturally want to select the `M` consecutive cows with the highest possible total "quality number."
For example, if the five cows in the circle are arranged as follows: 10, 3, 9, 7, 1.
Now, you need to buy 2 cows. Selecting the cows labeled 7 and 9 yields the maximum "quality score" sum of 16, which is your best choice.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input: The first line of each test case contains two numbers, N (1 <= N <= 10000) and M (1 <= M <= 5000). N indicates the number of cows in the corridor, and M indicates the number of cows you plan to purchase. A space separates the two numbers.
The next N lines contain an integer between 0 and 255, representing the "quality score" of each cow, given in clockwise or counterclockwise order. Note that the first cow and the last cow are adjacent in position. | For each input, output a single line containing the maximum sum of "quality scores" for the selected consecutive M cows. |
| 5 2 10 3 9 7 1 | 16 |
Thought Process
Record the prefix sums of the quality scores, and then evaluate the sum of the next `M` cows as you move from the beginning to the end. If you encounter a situation where you need to wrap around from the end to the beginning, first add the current quality scores you have, and then continue adding the remaining scores starting from the first position.
Sample Code－ZeroJudge D164: Best Choice
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, M;
while (cin >> N >> M) {
vector<int>prefix;
prefix.push_back(0);
int ans = -999;
for (int i = 1; i<=N; i++) {
int tmp;
cin >> tmp;
prefix.push_back(prefix[i-1]+tmp);
}
for (int i = 1; i<=N; i++) {
if (i + M - 1 <= N) {
const int calc = prefix[i+M-1] - prefix[i-1];
ans = max(ans, calc);
}
else {
int calc = prefix[N] - prefix[i-1];
const int left = M - (N-i+1);
calc += prefix[left] - prefix[0];
ans = max(ans, calc);
}
}
cout << ans << "\n";
}
}
//ZeroJudge D164
//Dr. SeanXD