题解洛谷P2503 【[HAOI2006]均分数据】

看了眼题目和数据范围\(n \leq 20,k \leq 6\)自然想到了\(dfs\)分组求解，主要是被这道题坑自闭过。

然而硬来\(dfs\)肯定会被蜜汁\(T\)掉，因为暴力\(n\)个数所在集合要跑\(n^k\)次。

于是又瞎猜了个贪心，即每次找到当前最小的集合\(p\)，将\(A_i\)放置集合\(p\)。

接着被我随脚出的一个数据愉快的\(hack\)掉了。

然后就突然想到了\(randomShuffle\)随机数大法

因为\(n\)个数是按顺序放置集合的，那么能不能考虑将这个数列多打乱几次从而枚举出不同的顺序\(?\)

简单权衡一下，整个贪心复杂度是\(O(nk)\)的，那么如果我们随机打乱数列\(T\)次，也就大大增加了贪心准确的概率。总复杂度\(O(nkT)\)。

测了一下，\(T\)开到\(500000\)也挺稳的呢。据说还可以用\(priority\)_\(queue\)来维护最小集合，优化到\(O(n logk T)\)，不过貌似还没必要。

\(Code:\)

#include<bits/stdc++.h>

using namespace std;

const int max_n=20+5,T=500000;

int n,k;

double a[max_n],f[max_n],x,ans=1e18;

void randomShuffle(){//随机打乱

    for(int i=1;i<=n;i++)swap(a[i],a[rand()%n+1]);

}

int Findmin(){//找最小集合

	int p,tot=1e18;

	for(int i=1;i<=k;i++){

		if(f[i]<tot)tot=f[i],p=i;

	}

	return p;

}

void solve(){

	memset(f,0,sizeof(f));

	for(int i=1;i<=n;i++){

		int p=Findmin();f[p]+=a[i];

	}

	double sum=0;

	for(int i=1;i<=k;i++){

		sum+=(f[i]-x)*(f[i]-x);

	}//计算均方差

	sum=sqrt(sum/k);ans=min(ans,sum);

}

int main(){

	ios::sync_with_stdio(false);

    srand((unsigned)time(NULL));

    cin>>n>>k;

    for(int i=1;i<=n;i++)cin>>a[i],x+=a[i];

    x=x/k;//x即为平均值

    for(int i=1;i<=T;i++)randomShuffle(),solve();

	printf("%.2lf\n",ans);

	return 0;

}

\(\operatorname{Update}\) \(\operatorname{On}\) \(\operatorname{2019.10.02}\)

巴特西

题解洛谷P2503 【[HAOI2006]均分数据】

最新文章

热门文章

巴特西

题解 洛谷P2503 【[HAOI2006]均分数据】

最新文章

热门文章

题解洛谷P2503 【[HAOI2006]均分数据】