和最大化最小值类似，最大化平均值也可以通过二分法求得。
 
比如下面这个经典的问题： 
 有n个物品的重量和价值分别是wi和vi，从中选出k个物品使得单位重量价值最大。
 
样例输入：
 
3 2
2 2
5 3
2 1
 
样例输出：
 
0.75
 
分析：
 
一般先想到的是将每个物品的单位重量价值算出来，然后排个序，从大到小贪心进行选择，可惜这样是不对的，这样不能保证最后一定是最大平均值，直接用贪心对于这类要涉及多个因素比如求最大平均值的问题就显得不那么正确了。
 
那么我们这样分析这个问题： 
 令C(x)为可以选择使得单位重量的价值不小于x。 
 这样就可以用二分法来解决，不断二分x进行判断，取最大。
 
我们继续分析：
 
 ∑vi / ∑wi 这个式子是我们需要求的单位重量的价值。 
 i∈s   i∈s
 
那么就求是否满足：
 
 ∑vi / ∑wi >= x
 i∈s   i∈s
 
转换一下得到：
 
∑(vi - x*wi) >= 0
i∈s 
 
判断这个式子是否成立即可。这下就可以用一个数组来保存vi - x * wi 的值，并进行排序，从大到小贪心地进行选择求和，如果求和的值大于0，那么此时 的x就是成立的。
 
代码如下：
 
#include<cstdio>
#include<algorithm> 
using namespace std;
const int maxn = 10000+10;
const int INF = 1000000;
int w[maxn],v[maxn];
double y[maxn];
int n,k;

bool C(double d)
{
    for(int i=0; i<n; i++)
    {
        y[i] = v[i] - d * w[i];
    }
    sort(y, y+n);

    double sum = 0;
    for(int i=0; i<k; i++)
    {
        sum += y[n-i-1];
    }
    return sum >= 0;
}
void solve()
{
    double lb = 0, ub = INF;
    for(int i=0; i<100; i++)
    {
        double mid = (lb + ub) / 2;
        if(C(mid)) lb = mid;
        else ub = mid;
    }
    printf("%.2f\n",lb);
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&w[i],&v[i]);
    }
    solve();
    return 0;
}

LeetCode 637 二叉树的层平均值
 
题目链接
 
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
 
示例 1：
 
输入：
 
    3
   / \
  9  20
    /  \
   15   7
 
输出：
 
[3, 14.5, 11]
 
典型的 BFS，每层算一个答案即可，AC代码如下:
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double>ans;
        queue<TreeNode*>q;
        TreeNode* t=root;
        q.push(t);
        while(!q.empty()){
            int siz=q.size();
            double a=0,b=double(q.size());
            while(siz--){
                t=q.front();q.pop();
                if(t!=NULL){
                    a+=t->val;
                    if(t->left)q.push(t->left);
                    if(t->right) q.push(t->right);
                }
            }
            ans.push_back(a/b);
        }
        return ans;
    }
};

 LeetCode 637. Average of Levels in Binary Tree
 
 
 Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
 
 
 
 Example 1:
 
 
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
 
 
 
 按照题目要求求解二叉树每层的平均值，既然按照层级求解，那么可以说是层次遍历或者说是BFS的典型问题。
 
 关键在于如何正确的在遍历过程中分层，思路是根据压入队列的元素个数划分。代码如下：
 
 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> v;
        if (root == NULL)
            return v;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            int num = q.size();
            long temp = 0;
            for (int i = 0; i < num; i++)
            {
                TreeNode *top = q.front();
                q.pop();
                if (top->left != NULL)
                    q.push(top->left);
                if (top->right != NULL)
                    q.push(top->right);
                temp += top->val;
            }
            v.push_back((double)temp / num);
        }
        return v;
    }
};

 

 
 

1、写在前面
 
平均值，标准差，方差，协方差都属于统计数学；期望属于概率数学。
 
统计数学
 
1）平均值，标准差，方差
 
统计学里最基本的概念就是样本的均值、方差、标准差。首先，我们给定一个含有n个样本的集合，下面给出这些概念的公式描述：
 
均值：
 
方差：
 
标准差：
 
均值描述的是样本集合的中间点，它告诉我们的信息是有限的。
 
方差（variance)是在概率论和统计方差衡量随机变量或一组数据时离散程度的度量。概率论中方差用来度量随机变量和其数学期望（即均值）之间的偏离程度。统计中的方差（样本方差）是各个数据分别与其平均数之差的平方的和的平均数。在许多实际问题中，研究方差即偏离程度有着重要意义。方差是衡量源数据和期望值相差的度量值。
 
而标准差给我们描述的是样本集合的各个样本点到均值的距离之平均。
 
以这两个集合为例，[0, 8, 12, 20]和[8, 9, 11, 12]，两个集合的均值都是10，但显然两个集合的差别是很大的，计算两者的标准差，前者是8.3后者是1.8，显然后者较为集中，故其标准差小一些，标准差描述的就是这种“散布度”。之所以除以n-1而不是n，是因为这样能使我们以较小的样本集更好地逼近总体的标准差，即统计上所谓的“无偏估计”。而方差则仅仅是标准差的平方。
 
方差和标准差的区别：
 
方差与我们要处理的数据的量纲是不一致的，多了个平方，虽然能很好的描述数据与均值的偏离程度，但是处理结果是不符合我们的直观思维的。 而标准差的根号就抵消了这个平方，就能相对直观了描述数据与均值之间的偏离程度。
 
2）协方差
 
标准差和方差一般是用来描述一维数据的，但现实生活中我们常常会遇到含有多维数据的数据集，最简单的是大家上学时免不了要统计多个学科的考试成绩。面对这样的数据集，我们当然可以按照每一维独立的计算其方差，但是通常我们还想了解更多，比如，一个男孩子的猥琐程度跟他受女孩子的欢迎程度是否存在一些联系。协方差就是这样一种用来度量两个随机变量关系的统计量，我们可以仿照方差的定义：
 
 
来度量各个维度偏离其均值的程度，协方差可以这样来定义：
 
 
协方差的结果有什么意义呢？如果结果为正值，则说明两者是正相关的（从协方差可以引出“相关系数”的定义），也就是说一个人越猥琐越受女孩欢迎。如果结果为负值， 就说明两者是负相关，越猥琐女孩子越讨厌。如果为0，则两者之间没有关系，猥琐不猥琐和女孩子喜不喜欢之间没有关联，就是统计上说的“相互独立”。
 
从协方差的定义上我们也可以看出一些显而易见的性质，如：
 
 
 
3）协方差矩阵
 
前面提到的猥琐和受欢迎的问题是典型的二维问题，而协方差也只能处理二维问题，那维数多了自然就需要计算多个协方差，比如n维的数据集就需要计算个协方差，那自然而然我们会想到使用矩阵来组织这些数据。给出协方差矩阵的定义：
 
 
这个定义还是很容易理解的，我们可以举一个三维的例子，假设数据集有三个维度，则协方差矩阵为：
 
 
可见，协方差矩阵是一个对称的矩阵，而且对角线是各个维度的方差。
 
概率论
 
1）期望（相当于统计数学中的均值）
 
离散型
 
离散型随机变量X的取值为，为X对应取值的概率，可理解为数据出现的频率，则：
 
 
 
连续型
 
 
2）方差
 
 
E(X)表示期望，X表示原始数据，其结果就为方差。当方差很小时，X的值形成的簇比较接近它们的期望值。方差的平方根被称为标准差(standard deviation)。D(X)还可以简化为：
 
 
 
 这里我是这么理解的：E的作用就是求平均，既然求完平均了，那么E(X)不就是一个常数了嘛，既然是常数了，拿平均自己那还是自己呀，也就是E(E(X))那不就是E(X)嘛。既然是这样那就好理解了，E(2XE(X))=2E(X)E(X)，E(X)的平方那也是常数，求平均还是自己。
 
 
另外再看一个例子：
 
 
 
 
 
 
3）标准差
 
方差的平方根被称为标准差(standard deviation)。简单来说，标准差是一组数值自平均值分散开来的程度的一种测量观念。一个较大的标准差，代表大部分的数值和其平均值之间差异较大；一个较小的标准差，代表这些数值较接近平均值。
 
这里标准差和方差的区别与统计学中一样。
 
均方误差
 
均方误差一般被用在机器学习的预测值与真实值之间的距离。
 
标准差（Standard Deviation），中文环境中又常称均方差，但不同于均方误差（mean squared error，均方误差是各数据偏离真实值的距离平方和的平均数，也即误差平方和的平均数，计算公式形式上接近方差，它的开方叫均方根误差，均方根误差才和标准差形式上接近），标准差是离均差平方和平均后的方根，用σ表示。标准差是方差的算术平方根。 
 从上面定义我们可以得到以下几点： 
 1、均方差就是标准差，标准差就是均方差 
 2、均方误差不同于均方差 
 3、均方误差是各数据偏离真实值的距离平方和的平均数 
 举个例子：我们要测量房间里的温度，很遗憾我们的温度计精度不高，所以就需要测量5次，得到一组数据[x1,x2,x3,x4,x5],假设温度的真实值是x，数据与真实值的误差e=x-xi 
 那么均方误差MSE= 
 总的来说，均方差是数据序列与均值的关系，而均方误差是数据序列与真实值之间的关系，所以我们只需要搞清楚真实值和均值之间的关系就行了。