Bài toán 2

Đề bài: Cho mảng a gồm n phần tử thực có các giá trị lớn nhất và nhỏ nhất lần lượt là Max và Min. Yêu cầu tính: 
$ Aver = \sum_{i=0}^{n-1}(a_i-Max)^2+\sum_{i=0}^{n-1}(a_i-Min)^2+\frac{n}{2}(Max-Min)^2$

Ý tưởng: 
Ta biến đổi
$ Aver = 2\sum_{i=0}^{n-1}a_{i}^2 - 2(Max+Min)\sum_{i=0}^{n-1}a_i + n(Max^2+Min^2) + \frac{n}{2}(Max-Min)^2$

Đến đây là chỉ cần i chạy từ 0 đến n-1 và tính bình thường, không cần phải lưu trữ mảng a lại.

Thuật toán: 

 Ta tính $S_2$, S bằng cách cộng dồn. Cuối cùng thế vào công thức đã biến đổi ở trên.

$ S_2 = \sum_{i=0}^{n-1}a_{i}^2;\ \ S = \sum_{i=0}^{n-1}a_{i} $

Mã nguồn:

#include <iostream>
using namespace std;
typedef double lf;

int main() {
int n;
lf x;
cin >> n;
cin >> x;
lf s2 = x*x, s1 = x, max = x, min = x;
        for (int i = 1; i < n; i++) {
cin >> x;
  s2 += x*x;
  s1 += x;
  if (x > max) max = x;
  if (x < min) min = x;
}
  lf ans = 2*s2-2*s1*(max+min)+n*(max*max+min*min)+n*(max-min)*(max-min)/2;
  cout << ans;
  system("Pause");
  return 0;
}