[ACM]求方差解决思路

2012-02-10

[ACM]求方差Time Limit:1000MSMemory Limit:10000KTotal Submit:87 Accepted:12Description给出M个数，从中

[ACM]求方差
Time Limit:1000MS Memory Limit:10000K
Total Submit:87 Accepted:12

Description

给出M个数，从中找出N个数，使这N个数方差最小。

Input

第一行
M,N (M > N, M ≤ 20)
第二行
M个整数

Output

最小的方差（结果保留小数点后一位）

Sample Input

3 2
1 2 3

Sample Output

0.2

就能想到穷举法。。杯具了。。。欢迎回帖讨论，期待大虾指导^_^

[解决办法]
排序，o(n log(n))
求排序后连续n个方差最小的。
利用Lxx＝∑(x^2)-(∑x)^2/N求方差，o(n)。
[解决办法]
菜鸟评论:
1)先排序
2)计算第一个和最后一个数的平均数,和中间的数比较判断出方差小的位置
3)判断方差小的位置数字个数如果小于所要输出的个数则在另一侧加入
否则把方差小的位置数字代入2) 重新计算

例如 5 2
10 5 7 9 1

1) 1 5 7 9 10
2) (1 + 10)/2 =5.5 5.5 < 7(7为中间数) 则可知方差小的位置为右侧
右侧个数为 3 大于输出个数 2
则把右侧数带入 2) 计算
7 9 10
(7 + 10)/2 = 8.5
8.5 < 9 则可知方差小的位置为右侧
又因为右侧个数为 2 等于输出个数2 则输出输出 9 10

(注上面例子中如果要输出4个数

2) (1 + 10)/2 =5.5 5.5 < 7(7为中间数) 则可知方差小的位置为右侧
右侧个数为 3 小于输出个数 4
则从右往左输出数字 10 9 7 5 (5 是从左侧加入的..)
)

[解决办法]
大概是这个意思吧，没仔细测试就放上来了。

C# code

using System;namespace CsdnTest{    class Program    {        static void Main(string[] args)        {            string[] inputValues = Console.ReadLine().Split(' ');            int m = int.Parse(inputValues[0]);            int n = int.Parse(inputValues[1]);            int[] items = new int[m];            int[] acc = new int[m + 1];            for (int i = 0; i < m; i++)                items[i] = int.Parse(Console.ReadLine());            Array.Sort(items);            for (int i = 1; i <= m; i++)                acc[i] = acc[i - 1] + items[i - 1];            int sqrSum = 0;            double avg, sqrD, min = acc[m] * acc[m];            for (int i = 0; i < m; i++)            {                sqrSum += items[i] * items[i];                                if (i >= n)                    sqrSum -= items[i - n] * items[i - n];                if (i >= n - 1)                {                    avg = (double)(acc[i + 1] - acc[i - n + 1]) / n;                    sqrD = (double)sqrSum / n - avg * avg;                    if (sqrD < min)                        min = sqrD;                }            }            Console.WriteLine(Math.Round(min,1, MidpointRounding.ToEven));        }    }}
[解决办法]
经典之作：
看一下：里面有你想要的：
http://download.csdn.net/source/2279977

热点排行

软件架构设计

[ACM]求方差解决思路