【题解】【数组】【Prefix Sums】【Codility】Min Average Two Slice

Find the minimal average of any slice containing at least two elements.

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q ? P + 1).

For example, array A such that:

A[0] = 4 A[1] = 2 A[2] = 2 A[3] = 5 A[4] = 1 A[5] = 5 A[6] = 8

contains the following example slices:
slice (1, 2), whose average is (2 + 2) / 2 = 2;
slice (3, 4), whose average is (5 + 1) / 2 = 3;
slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
The goal is to find the starting position of a slice whose average is minimal.

the function should return 1, as explained above.
Assume that:
N is an integer within the range [2..100,000];
each element of array A is an integer within the range [?10,000..10,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

思路：

这题跟Prefix Sums有关系，但也不能直接套，有两个很重要的点

1 MinAvgSlice其子片段的Avg都是相等的，不然就可以只保留Avg较小的子片段

2  最小的不可分割的子片段必然是2Slice或者3Slice(4Slice可以分割为两个2Slice)

观察到这两点之后，只需要构建Prefix Sums数组，再遍历一遍寻找最小的2Slice/3Slice即可，有个家伙对这两点给出了证明

实现上只需注意在除2除3的时候变为除2.0和除3.0

代码：

 1 int solution(vector<int> &A) {
 2     int n = A.size();
 3     double min_avg_value = (A[0]+A[1])/2.0;
 4     int min_avg_pos = 0;
 5     
 6     for(int i = 0;i < n - 2;i++){
 7         if((A[i]+A[i+1])/2.0 < min_avg_value){
 8             min_avg_value = (A[i]+A[i+1])/2.0;
 9             min_avg_pos = i;
10         }
11         if((A[i]+A[i+1]+A[i+2])/3.0 < min_avg_value){
12             min_avg_value = (A[i]+A[i+1]+A[i+2])/3.0;
13             min_avg_pos = i;
14         }
15     }
16     if((A[n-2]+A[n-1])/2.0 < min_avg_value){
17         min_avg_value = (A[n-2]+A[n-1])/2.0;
18         min_avg_pos = n-2;
19     }
20     return min_avg_pos;
21 }

【题解】【数组】【Prefix Sums】【Codility】Min Average Two Slice

原文：http://www.cnblogs.com/wei-li/p/MinAvgTwoSlice.html