BZOJ2428 均分数据
2024-10-13 18:19:00
2428: [HAOI2006]均分数据
Time Limit: 5 Sec Memory Limit: 128 MB
Description
已知N个正整数:A1、A2、……、An 。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:
,其中σ为均方差,是各组数据和的平均值,xi为第i组数据的数值和。
Input
第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)
第二行有N个整数,表示A1、A2、……、An。整数的范围是1--50。
(同一行的整数间用空格分开)
Output
这一行只包含一个数,表示最小均方差的值(保留小数点后两位数字)。
Sample Input
6 3
1 2 3 4 5 6
1 2 3 4 5 6
Sample Output
0.00
HINT
对于全部的数据,保证有K<=N <= 20,2<=K<=6
AC+1
模拟退火,随机选点更换分组
当温度太大不稳定,直接尝试换到sum最小的组
由于模拟退火的不稳定,所以跑个几万遍就稳了233
当然如果您是yzh那样的强者,您可以用DP每次算最优解
个人认为这样并不优秀,如果您有心情$n ^ 2 m$DP,为何不多退$n ^ 2 m$次火<_<
#include<bits/stdc++.h>
using namespace std;
template <class _T> inline void read(_T &_x) {
int _t; bool flag = false;
while ((_t = getchar()) != '-' && (_t < '0' || _t > '9')) ;
if (_t == '-') _t = getchar(), flag = true; _x = _t - '0';
while ((_t = getchar()) >= '0' && _t <= '9') _x = _x * 10 + _t - '0';
if (flag) _x = -_x;
}
using namespace std;
const int maxn = 30;
int n, m, a[maxn];
double ave;
int from[maxn], sum[maxn];
inline double sqr(double val) {return val * val; }
inline double getr() {return (double)rand() / RAND_MAX; }
inline double solve() {
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; ++i) {
from[i] = rand() % m + 1;
sum[from[i]] += a[i];
}
double ans = 0;
for (int i = 1; i <= m; ++i)
ans += sqr(sum[i] - ave);
double T = 10000;
while (T > 0.1) {
int t = rand() % n + 1, x = from[t], y;
if (T > 1000) y = min_element(sum + 1, sum + m + 1) - sum;
else y = rand() % m + 1;
double to = ans;
to -= sqr(sum[x] - ave) + sqr(sum[y] - ave);
to += sqr(sum[x] - a[t] - ave) + sqr(sum[y] + a[t] - ave);
if (to < ans || exp((ans - to) * 1e4 / T) > getr()) {
ans = to;
from[t] = y;
sum[x] -= a[t], sum[y] += a[t];
}
T *= 0.9;
}
return ans;
}
int main() {
//freopen();
//freopen();
srand(19260817);
read(n), read(m);
for (int i = 1; i <= n; ++i) {
read(a[i]);
ave += a[i];
}
ave /= m;
double ans = solve();
for (int i = 1; i <= 10000; ++i)
ans = min(ans, solve());
printf("%.2lf\n", sqrt(ans / m));
return 0;
}
最新文章
- javaScript生成二维码(支持中文,生成logo)
- html基础学习
- [Java面试十]浏览器跨域问题.
- 如何阻止h5body的滑动
- 05章项目: QuickHit快速击键
- MVPHelper
- redis面试
- 高效的DDoS攻击探测与分析工具——FastNetMon
- codevs 1036 商务旅行 (倍增LCA)
- Best Time to Buy and Sell Stock II ——LeetCode
- PHP 调用asp.net Web Services服务问题总结
- Jquery实现表格的分页
- 基于Petri网的工作流分析和移植
- 知识点练习day9
- Iframe父页面与子页面之间的相互调用
- 2015 多校联赛 ——HDU5363(快速幂)
- SQL2008R2的 遍历所有表更新统计信息 和 索引重建
- jdk8 永久代变更
- 网页布局设计css中单位px和em,rem的区别
- MBProgressHUD 的类扩展方法用法
热门文章
- Azkaban集群部署
- Python数据信号处理库RadioDSP: 引入ThinkDSP实现思想
- LevelDB原理解析
- VGGNet论文翻译-Very Deep Convolutional Networks for Large-Scale Image Recognition
- webug4.0安装
- 互评Final版本——二次元梦之队——“I Do”
- Design and Implementation of a Routing Control Platform阅读笔记
- 腾讯云申请的64位ubuntu服务器配置php环境
- 组件 -- Alert
- jQuery~DOM基础操作