Codeforces 912D(期望+BFS)

Codeforces 912D
题意：有一个$n \times m$的鱼塘，有一张$r \times r$的渔网，现在往池塘里面放$k$条鱼(每个格子只能放一条鱼)， 现在撒网的地方是随机的(必须在池塘内)，问能捕的鱼的期望值最大是多少？

原题的期望值为
$$\frac{\sum max_k(f(i,j))}{(n - r + 1)(m - r + 1)}$$
其中$f(i,j)$为$r \times r$的网在鱼塘$(i,j)$点上总共会撒的次数，$max_k$表示最大的$k$个数

然后可以证明从中间开始是最优的，我们可以BFS来模拟这个过程，但是要用一个优先队列保证每次取的都是最大值

代码中的$cal$就是上述公式的$f$函数

Codeforces Submission

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
#define db double
#define pr pair<int, int>
#define fir first
#define sec second
#define mp make_pair
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, 1, 0, -1};
ll n, m, r, k;
set<pr> s;
struct data {
    ll x, y, v;
    bool operator < (const data &b) const {
        return v < b.v;
    }
};
priority_queue<data> q;
ll cal(ll i, ll j) {
    return 1ll * (min(i, n - r + 1ll) - max(1ll, i - r + 1ll) + 1ll) * (min(j, m - r + 1ll) - max(1ll, j - r + 1ll) + 1ll);
}
void clean() {
}
int solve() {
    clean();
    if (n == 1 || m == 1) {
        printf("%.10f\n", (db)k / (db)((db)n * (db)m));
        return 0;
    }
    ll fz = 0, fm = (n - r + 1) * (m - r + 1);
    q.push((data){(n + 1) / 2, (m + 1) / 2, cal((n + 1) / 2, (m + 1) / 2)});
    s.insert(mp((n + 1) / 2, (m + 1) / 2));
    while (!q.empty()) {
        data p = q.top(); q.pop();
        fz += p.v;
        k--; if (!k) break;
        for (ll i = 0; i < 4; i++) {
            ll tx = p.x + dx[i], ty = p.y + dy[i];
            if (tx > 0 && ty > 0 && tx <= n && ty <= m && !s.count(mp(tx, ty))) {
                q.push((data){tx, ty, cal(tx, ty)});
                s.insert(mp(tx, ty));
            }
        }
    }
    printf("%.10f\n", (db)fz / (db)fm);
    return 0;
}
int main() {
    cin >> n >> m >> r >> k, solve();
    return 0;
}