洛谷P2503 [HAOI2006] 均分数据 题解 模拟退火
  t7gYRacb89cM 2023年11月02日 32 0

题目链接:https://www.luogu.com.cn/problem/P2503

模拟退火 + 贪心。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[22], s[22], cnt[22];
double avga, ans = 1e9;

double cal() {
    memset(s, 0, sizeof(int)*m);
    memset(cnt, 0, sizeof(int)*m);
    for (int i = 0; i < n; i++) {
        int x = 0;
        for (int j = 1; j < m; j++)
            if (s[j] < s[x])
                x = j;
        s[x] += a[i];
        cnt[x]++;
    }
    double sum = 0;
    for (int i = 0; i < m; i++) {
        double dx = (double) s[i] - avga;
        sum += dx * dx;
    }
    sum = sqrt(sum / m);
    ans = min(ans, sum);
    return sum;
}

void sa() {
    random_shuffle(a, a+n);
    for (double t = 1e4; t >= 1e-4; t *= 0.993) {
        double cur = cal();
        int p = rand() % n, q = rand() % n;
        if (p == q) continue;
        swap(a[p], a[q]);
        double tmp = cal();
        double dt = tmp - cur;
        if (exp(-dt / t) < (double) rand() / RAND_MAX) {
            ;
        }
        else
            swap(a[p], a[q]);
    }
}

int main() {
    srand(time(NULL));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", a+i), avga += a[i];
    avga /= m;
    for (int i = 0; i < 500; i++)
        sa();
    printf("%.2lf\n", ans);
    return 0;
}

三分天注定,七分靠人品。上面代码多提交几次,总还是能AC的。



【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  8Tw5Riv1mGFK   2024年05月01日   80   0   0 C++
  BYaHC1OPAeY4   2024年05月08日   56   0   0 C++
  yZdUbUDB8h5t   2024年05月05日   43   0   0 C++
  oXKBKZoQY2lx   2024年05月17日   57   0   0 C++
t7gYRacb89cM