美高梅网投网站-美高梅手机网投-美高梅官方网站
做最好的网站

您的位置:美高梅网投网址 > 美高梅手机网投 > 美高梅网投网站第二行有N个整数

美高梅网投网站第二行有N个整数

发布时间:2019-09-25 03:08编辑:美高梅手机网投浏览(78)

    题目描述

    已知N个正整数:A1、A2、……、An 。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:

    美高梅手机网投 1

    我大概是中毒了。。。。
    对模拟退火 走火入魔了
    这随机数算法。。。啧。。。
    感觉有毒。

    输入输出格式

    输入格式:

    输入文件data.in包括:

    第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)

    第二行有N个整数,表示A1、A2、……、An。整数的范围是1--50。

    (同一行的整数间用空格分开)

    输出格式:

    输出文件data.out包括一行,这一行只包含一个数,表示最小均方差的值(保留小数点后两位数字)。

    BZOJ2428: [HAOI2006]均分数据
    【洛谷P2503】
    已知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
    Sample Output 0.00

    输入输出样例

    输入样例#1:复制

    6 31 2 3 4 5 6
    

    输出样例#1:复制

    0.00
    

    对于全部的数据,保证有K<=N <= 20,2<=K<=6

    说明

    样例解释:1和6、2和5、3和4分别为一组

    对于40%的数据,保证有K<=N <= 10,2<=K<=6

    对于全部的数据,保证有K<=N <= 20,2<=K<=6

    直接强上模拟退火

    随机出每个位置在哪个地方

    然后每次任意取出一个元素,加到最小的分组中

    exp的设定就按套路来,用更新后的值减去之前的值

    然后在BZOJ上T飞了

    // luogu-judger-enable-o2#include<cstdio>#include<cmath>#include<ctime>#include<cstdlib> #include<algorithm>#include<cstring>#define sqr*const int MAXN = 31;const double eps = 1e-15;const int INF = 1e9 + 10;using namespace std;inline int read() {    char c = getchar();int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}    return x * f;}int N, M;int belong[MAXN], a[MAXN];double sum[MAXN], Aver = 0, Best = 1e20;void MoNiTuiHuo() {    memset(sum, 0, sizeof;    const double DeltaT = 0.99;    double ans = 0;    for(int i = 1; i <= N; i++) belong[i] = rand() % M + 1, sum[ belong[i] ] += a[i];    for(int i = 1; i <= M; i++) ans += sqr(sum[i] - Aver);    for(double T = 10000; T > eps; T *= DeltaT) {        int P = min_element(sum + 1, sum + M + 1) - sum;//找出最小的位置         int X = rand() % N + 1;//这里直接随机就可以         double Pre = ans;        ans -= sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver);        sum[ belong[X] ] -= a[X]; sum[P] += a[X];        ans += sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver);                if((ans < Pre) || (exp( /T ) * RAND_MAX  < rand belong[X] = P;//以一定概率接受最优解         else ans = Pre, sum[ belong[X] ] += a[X], sum[P] -= a[X];    //不更新     }    if(ans < Best)         Best = ans;}int main() {    #ifdef WIN32    freopen("a.in", "r", stdin);    #endif    srand(19260817);    N = read(); M = read();    for(int i = 1; i <= N; i++) a[i] = read(), Aver += a[i];    Aver /= M;    for(int i = 1; i <= 1000; i++) MoNiTuiHuo();    printf("%.2lf",sqrt);//因为y=sqrt这个函数具有单调性,所以最后在开根就可以     return 0;}
    
    #include<cmath>
    #include<cstdlib>
    #include<cstdio>
    #include<ctime>
    #define llf double
    using namespace std;
    const int N=101;
    const int TIME=5000;
    const llf INF=2147483647;
    int n,m,a[N];
    llf ave,mn=INF;
    llf pf(llf x){return x*x;}
    void work(){
        llf ans=0,T=10000;
        int x[N]={0},bl[N]={0};
        //随机分组
        for(int i=1;i<=n;i++){
            int grp=rand()%m+1;
            bl[i]=grp;x[grp]+=a[i];
        }for(int i=1;i<=m;i++)
            ans+=pf(x[i]-ave);
        //开始降温
    
        while(T>0.1){
            //随机出来一个需要调整的数字 
            int t=rand()%n+1,u=bl[t],v;
            llf tmp=ans; T*=0.9;
    
            if(T>500){
                int grp;llf mnx=INF;
                for(int i=1;i<=m;i++)
                if(i!=u&&x[i]<mnx)
                    mnx=x[i],grp=i;
                v=grp;
            }else {
                v=rand()%m+1;
                while(u==v)v=rand()%m+1;
            }
            //把这个数字从这组转到另一组 
            ans-=pf(x[u]-ave)+pf(x[v]-ave);
            x[u]-=a[t];x[v]+=a[t];
            ans+=pf(x[u]-ave)+pf(x[v]-ave);
            //答案合适 就看命修改 
            if(ans>tmp&&(rand()%10000>T))
                ans=tmp,x[u]+=a[t],x[v]-=a[t];
            else bl[t]=v;
        }if(ans<mn)mn=ans;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            ave+=a[i];
        }   ave/=m;
        for(int i=1;i<=TIME;i++) work();
        printf("%.2lfn",sqrt(mn/m));
        return 0;
    }
    

    好像也挺好玩的???23333.
    貌似难在时间复杂度的把握上(⊙o⊙)

    本文由美高梅网投网址发布于美高梅手机网投,转载请注明出处:美高梅网投网站第二行有N个整数

    关键词:

上一篇:没有了

下一篇:没有了