题意简述:往n*m的网格中放k条鱼,一个网格最多放一条鱼,然后用一个r*r的网随机去捞鱼,问怎么怎么放鱼能使得捞鱼的期望最大,输出这个期望

题解:肯定优先往中间放,这里k不大,因此有别的简单方法,否则推公式各种情况烦死人,我们对于每一行来说将中间的数加进去,然后用set来维护k次就好了

#include<bits/stdc++.h>
#define forn(i, n) for (int i = 0 ; i < int(n) ; i++)
#define fore(i, s, t) for (int i = s ; i < (int)t ; i++)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf(x) printf("%d\n",x)
#define each(x) for(auto it:x) cout<<it<<endl;
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const int maxm=2e5+5;
const int inf=1e9;
int n,m,r,k;
struct cell{
int x,y,d;
ll val;
cell(int x,int y,int d):x(x),y(y),d(d){
val=(min(m+1,y+r)-max(y,r))*1ll*(min(n+1,x+r)-max(x,r));
}
bool operator<(const cell& rhs)const {
return val>rhs.val;
}
};
multiset<cell> ms;
double calc(){
for (int i = 1; i <= n; i++) {
int j = m / 2;
ms.insert({ i, j, 0 });
ms.insert({ i, j + 1, 1 });
}
ll total = 0;
for(int i=0;i<k;i++){
auto it = *ms.begin();
total += it.val;
ms.erase(ms.begin());
if (it.d == 1 && it.y < m)
ms.insert({ it.x, it.y + 1, 1 });
else if (it.d == 0 && it.y > 1)
ms.insert({ it.x, it.y - 1, 0 });
}
return (double)total / ((n - r + 1) * 1LL * (m - r + 1));
}
int main(){
cin>>n>>m>>r>>k;
if(n>m) swap(n,m);
if(m==1) {
printf("%.10f\n",1.0);
}
else {
printf("%.10f\n",calc());
}
}

  

最新文章

  1. [转]10个有关RESTful API良好设计的最佳实践
  2. eclipse导入外部jar包
  3. 转载:jQuery实现返回顶部功能
  4. 上中下三个DIV,高度自适应(上高度固定,下固定,中间自适应)(代码来自X人)
  5. Java观察者模式(Observer模式)
  6. Unity ShaderLab学习总结
  7. #MySQL for Python(MySQLdb) Note
  8. java加密与解密
  9. Learning Puppet — Resources and the RAL
  10. 【MongoDB】增删改查基本操作
  11. 设计模式 Mixin (混入类)
  12. D - 金樽清酒斗十千(搜索dfs)
  13. Spark的分布式计算
  14. RHM-M60型挖掘机力矩限制器/载荷指示器
  15. linux备份还原命令
  16. python全栈开发 * background 定位 z-index * 180813
  17. Java中对List集合的常用操作
  18. svn提示文件 is already locked
  19. Gym - 101617F :Move Away (圆的交点)
  20. MXNET:权重衰减-gluon实现

热门文章

  1. vue报错Error in v-on handler: &quot;RangeError: Maximum call stack size exceeded&quot;
  2. 使用abp框架与vue一步一步写我是月老的小工具(1)
  3. hashmap 的边遍历边存储
  4. css: line-height 与box-sizing
  5. CCF_201604-3_路径解析
  6. Codeforces 1178E Archaeology (鸽巢原理)
  7. java架构之路-(微服务专题)初步认识微服务与nacos初步搭建
  8. Java中类的关系
  9. javascript检测客户端环境是否是pc端
  10. 前端添加复选框checkbox 提交到django后台处理