「HAOI2006」均分数据

今天是国际劳动妇女节,各位妇女们有没有去劳动啊QwQ?反正我没去

传送门

洛谷P2503

BZOJ2428

题解

数据范围好小啊,看起来像是状压DP或者搜索之类的。蒟蒻我选择了模拟退火+贪心。

先考虑贪心,我们从$1$到$n$遍历整个序列,每次就把当前的元素丢到加和最小的那一组里。

显然光光这样贪心是肯定不行的,但是这样得到的答案还是比较优的。考虑怎样改进。

不难发现,如果遍历序列的顺序会影响最后的答案,那么可以考虑直接random_shuffle,打乱个比如$10^5​$次的,很大概率上就能刷到最优解了。

但是总感觉直接random_shuffle不太靠谱啊(不过貌似也能AC),但是蒟蒻我选择了模拟退火,感觉起来会靠谱一些(其实到底是不是更靠谱我也不知道,但是我想练一下模拟退火,所以就这样写了)。

每次随机拎出来两个元素交换,然后再计算当前答案就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=25,maxm=10;const double delta=0.991;
int n,m,A[maxn];double X[maxn],avg,ret,ans;
inline double Calc() //计算当前答案
{
ret=avg=0;
memset(X,0,sizeof(X));
for(int i=1;i<=n;i++)
{
int mi=1;
for(int j=1;j<=m;j++)
if(X[j]<X[mi])
mi=j;
X[mi]+=A[i];
}
for(int i=1;i<=m;i++) avg+=X[i];
avg/=m;
for(int i=1;i<=m;i++) ret+=(X[i]-avg)*(X[i]-avg);
return sqrt(ret/m);
}
inline void SA(double T)
{
while(T>1e-12)
{
int a=rand()%n+1,b=rand()%n+1;
while(a==b){a=rand()%n+1;b=rand()%n+1;}//rand出来两个是一样的概率挺大的,这样可以提升效率
swap(A[a],A[b]);
double now=Calc();
if(now<ans) ans=now;
else if(exp((ans-now)/T)<(double)rand()/RAND_MAX) swap(A[a],A[b]);
T*=delta;
}
}
int main()
{
srand(20030909); //黄霖的生日,种子什么的选大佬的生日肯定不会错的
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&A[i]);
sort(A+1,A+1+n);
ans=Calc();
for(int i=1;i<=100;i++) SA(19630217); //退火100次又不会WA并且还比较快,求稳的话可以多来几次
printf("%.2lf\n",ans);
return 0;
}