CF912D Fishes

题目链接：http://codeforces.com/contest/912/problem/D

题目大意：

　　在一个\(n \times m\)的网格中放鱼（每个网格只能放一条鱼），用一个\(r \times r\)的网随机地捕一次鱼，问如何放置鱼能使得捕到的鱼的期望值最大，求最大值。

知识点：　　优先队列、概率与期望

解题思路：

　　要使捕到鱼的期望值最大，就应该往最有可能被渔网捞到的格子里放鱼。

　　\(P(某个格子被捞到）= N_1(渔网能捞到这个格子的放置方案数)/N_2(渔网总放置方案数),\)

　　\(N(渔网总放置方案数) = (n-r+1)\times(m-r+1)\)

　　而要求\(N_1\)，我们可以先算出最左边一列和最上边一行的各个格子对应的\(N_1\)，\(N_1(x,y) = N_1(x,0) \times N_1(0,y)\)。于是我们可以从最中间的格子开始（直觉告诉我们：最中间的格子总是最有可能被捞到）,用一个优先队列维护，每次都往上下左右四个方向拓展，找出前 \(k\) 个最有可能被捞到的位置所对应的期望值，加起来所得到的总和即为答案。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 1e5+;

 const int cx[]={,-,,},cy[]={,,,-};

 int line[maxn],col[maxn];

 struct node{

     int x,y;

     double z;

     friend bool operator <(const node &a,const node &b){

         return a.z<b.z;

     }

 };

 map<pair<int,int>,int> vis;

 priority_queue<node> q;

 int main(){

     int n,m,r,k;

     scanf("%d%d%d%d",&n,&m,&r,&k);

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

         if(i<=n-r+)    line[i]=min(i,r);

         else    line[i]=line[i-];

     }

     for(int i=n,j=;i>(n+)/;i--,j++)

         line[i]=line[j];

     for(int i=;i<=(m+)/;i++){

         if(i<=m-r+)    col[i]=min(i,r);

         else    col[i]=col[i-];

     }

     for(int i=m,j=;i>(m+)/;i--,j++)

         col[i]=col[j];

     double tot=(double)(n-r+)*(m-r+),ans=0.0;

     node now,next;

     now.x=(n+)/,now.y=(m+)/;

     now.z=(double)line[now.x]*col[now.y]/tot;

     q.push(now);

     vis[make_pair(now.x,now.y)]=;

     while(k--){

         now=q.top();

         q.pop();

         ans+=now.z;

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

             int nx=now.x+cx[i],ny=now.y+cy[i];

             if(nx>&&nx<=n&&ny>&&ny<=m&&!vis[make_pair(nx,ny)]){

                 next.x=nx,next.y=ny,next.z=(double)line[next.x]*col[next.y]/tot;

                 q.push(next);

                 vis[make_pair(nx,ny)]=;

             }

         }

     }

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

     return ;

 }