病人康复(C++ 滑动窗口)

Challenge 3 description

A patient needs rehabilitation within the next N days (numbered from 0 to N-1). The rehabilitation consists of X sessions. For every
rehabilitation session, other than the last one, the next session is
exactly Y days later.
You are given an array A of N integers listing the costs of the individual rehabilitation sessions on the N days: that is rehabilitation on the K-th day costs A[K].
Write a function:

int solution (int Al], int N, int X, int Y):
1

that, given the array A and the two integers X and Y, returns the
minimum cost of rehabilitation.
It is guaranteed that it is always possible to complete all X
rehabilitation sessions.
Examples:

1. Given A = [4, 2, 3, 7], X = 2 and Y = 2, your function should return 7,
   which is the sum of the costs on days 0 and 2 (7 = 4 + 3).
2. Given A = [10, 3, 4, 7], X = 2 and Y = 3, your function should return 17 since rehabilitation is possible only on days 0 and 3 (17 = 10 + 7).
3. Given A = [4, 2, 5, 4, 3, 5, 1, 4, 2, 7], X = 3 and Y = 2, your function should return 6, which is the sum of the costs on days 4, 6 and 8 (6 = 3 + 1 + 2).

Write an efficient algorithm for the following assumptions:

• N and X are integers within the range [2…200,000];
• each element of array A is an integer within the range [1…1,0001]
• Y is an integer within the range [1…199,999];
• N is higher than (X - 1) * Y.

分析

滑动窗口，不这样的话会多很多重复计算，会超时。

#include 

using namespace std;

/// 核 心 代 码 // 
int solution(int A[], int N, int X, int Y) {
    int res = 0x7FFFFFFF;
    for (int i = 0; i < Y; i++) {
        int count = 0;
        int sum = 0;
        int start = i;
        int end = i;
        while (end < N) {
            sum += A[end]; // 这里是[end]! 粗心写成 i 了，结果老是错, 我是shabby
            count++;
            if (count == X) {
                res = res<sum?res:sum;
                sum -= A[start];
                start += Y;
                count--;
            }
            end += Y;
        }
    }
    return res;
}
/// 核 心 代 码 //

int main () {
    int A[] = {4, 2, 5, 4, 3, 5, 1, 4, 2, 7};
    int B[] = {4, 2, 3, 7};
    cout << solution(A, 10, 3, 2) << endl;
    cout << solution(B, 4, 2, 2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35