51nod 1098 最小方差 贪心+前缀和+公式化简

2023-11-09 23:58

本文主要是介绍51nod 1098 最小方差 贪心+前缀和+公式化简,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1098 最小方差

  1. 1.0 秒
  2.  
  3. 131,072.0 KB
  4.  
  5. 20 分
  6.  
  7. 3级题

若x1,x2,x3......xn的平均数为k。

则方差s^2 = 1/n * [(x1-k)^2+(x2-k)^2+.......+(xn-k)^2] 。

方差即偏离平方的均值,称为标准差或均方差,方差描述波动程度。

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

输入

第1行:2个数M,N,(M > N, M <= 10000)
第2 - M + 1行:M个数的具体值(0 <= Xi <= 10000)

输出

输出最小方差 * N的整数部分。

输入样例

5 3
1
2
3
4
5

输出样例

2

 

分析:贪心+前缀和。

先对原始数据排序,由于方差反应稳定程度。故那么我们选取的N个数一定是连续的。利用一下前缀和就可以过这个题。

不过还可以更优化:

来自:https://blog.csdn.net/qq_41289920/article/details/82025314

代码一:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e18;
const int N = 5000050;
int n,m;
LL a[N];
LL sum[N];
long double fancha(int l,int r)
{double  avg=(1.0*(sum[r]-sum[l-1]))/(1.0*m);long double temp=0;for(int i=l; i<=r; i++){temp+=(a[i]-avg)*(a[i]-avg);}// cout<<l<<" "<<r<<" "<<temp<<endl;return temp;
}
int main()
{long double ans=1e18;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%lld",&a[i]);}sort(a+1,a+n+1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}for(int i=1; i+m-1<=n; i++){int j=i+m-1;ans=min(ans,fancha(i,j));}printf("%lld\n",(LL)floor(ans));return 0;
}

代码二

 

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e18;
const int N = 5000050;
int n,m;
LL a[N];
LL sum[N],sum1[N];
long double fancha(int l,int r)
{return  1.0*(sum1[r]-sum1[l-1])-1.0*(sum[r]-sum[l-1])*(sum[r]-sum[l-1])/m;
}
int main()
{long double ans=1e18;scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%lld",&a[i]);}sort(a+1,a+n+1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];sum1[i]=sum1[i-1]+a[i]*a[i];}for(int i=1; i+m-1<=n; i++){int j=i+m-1;ans=min(ans,fancha(i,j));}printf("%lld\n",(LL)floor(ans));return 0;
}

 

这篇关于51nod 1098 最小方差 贪心+前缀和+公式化简的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/379208

相关文章

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回