第四届西安邮电大学acm-icpc校赛 猜球球
2024-08-28 14:35:39
题目描述
六一到了，为了庆祝这个节日，好多商家都推出了很多好玩的小游戏。Tongtong看到了一个猜球球的游戏，有n种除了颜色之外完全相同的球，商家从中拿出来一个球球放到了箱子里，已知第i种颜色的球出现在箱子里的概率为ai。Tongtong可以用下面这种方法来确定箱子中球的颜色：向商家提出猜测：“是第x种颜色的球球或第y种颜色的球球或...........中的一个”，商家会回答你的猜测是正确还是错误的，直到你有百分百的把握确定箱子里的球球，猜测的次数越少，Tongtong能够得到的礼物就更好。为了让Tongtong过一个开开心心的六一，请你找出一种最优的策略，尽可能少的向店主提出猜测来确定球的颜色，输出猜测次数的期望值。
策略“最优”是指：猜测次数的期望最小。当你有百分百的把握确定箱子里的球球颜色种类时，则不需要继续猜测。例如，如果有两种颜色的球球，箱子里放的是第二种颜色的球球，你可以猜测“是第一种颜色的球球”。商家会告诉你“错误”，所以你可以推测“箱子里的球球是第二种颜色的”，并且有百分百的把握，所以你就可以结束猜测而不需要额外的一次猜测。这种询问方式猜测次数为一次（不管你这一次有没有猜对）。
策略“最优”是指：猜测次数的期望最小。当你有百分百的把握确定箱子里的球球颜色种类时，则不需要继续猜测。例如，如果有两种颜色的球球，箱子里放的是第二种颜色的球球，你可以猜测“是第一种颜色的球球”。商家会告诉你“错误”，所以你可以推测“箱子里的球球是第二种颜色的”，并且有百分百的把握，所以你就可以结束猜测而不需要额外的一次猜测。这种询问方式猜测次数为一次（不管你这一次有没有猜对）。
输入
第一行输入一个n，表示有n种颜色的球。 n<=2 000
第二行输入n个非负小数a1~an，表示是第i种颜色球球的概率，保证加和起来为1。
第二行输入n个非负小数a1~an，表示是第i种颜色球球的概率，保证加和起来为1。
输出
输出最小期望，保留7位小数。
样例输入
3
0.5000000000 0.2500000000 0.2500000000
样例输出
1.5000000
提示
最佳策略下：第一次询问“是不是第二种颜色的球球或第三种颜色的球球中的一种”，如果回答“否”则可以知道是第一种颜色的球球，结束询问；如果回答是“是”则询问第二次“是不是第二种颜色的球球”。
官方题解：
因为任意一次询问和回答，都可以确定其中一半的球球集合包含目标球，另一半则不包含目标球。然后再对包含目标球的球球集合进一步划分，直到包含目标球的集合里只包含一个球，就可以百分百确定了。这样就得到了一个决策树（二叉形状），二叉决策树根节点到每个叶子的路到都是期中一种情况的解决方案，显然深度就是询问次数。 则有：期望=∑(询问次数*每种情况出现的概率)=∑(叶子对应的深度*它出现在盒子里的概率)。 而我们知道：这个公式 ∑（深度*元素出现的概率 ） 与某种编码方案的编码长度期望公式 相同。询问次数的期望最小也就是编码长度的期望最小。而解决这个问题的经典方法就是——哈夫曼树
然后需要注意的是，概率为0的球不用放入优先队列中。
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n))
{
priority_queue<double,vector<double>,greater<double> > q;
double x,y,ans=0.0;
while(n--)
{
scanf("%lf",&x);
if(x>0.0)
q.push(x);
}
while(q.size()>)
{
x=q.top();
q.pop();
y=q.top();
q.pop();
ans+=x+y;
q.push(x+y);
}
printf("%.7lf\n",ans);
}
return ;
}
哈夫曼树
最新文章
- ms-sql关联表操作
- eclipse查看class文件的源码
- poj2236(并查集)
- jQuery 3.1.1 官方下载地址
- 【Linux】基于Bind_DLZ和MySQL数据的DNS搭建
- 用Canvas制作小游戏——贪吃蛇
- Java多线程初学者指南（8）：从线程返回数据的两种方法
- C语言－for循环
- keepalive配置文件详解
- Docker 创建 Bamboo6.7.1 以及与 Crowd3.3.2 实现 SSO 单点登录
- IDEA安装插件提示was not installed: Cannot download解决办法
- 烧写树莓派系统，SSH配置，无屏登录流程
- 最大公约数&&最小公倍数
- win2008以上的系统，在vmware esxi5.5里怎么使用自定义规范管理器？sysprep
- ubuntu emacs的安装
- 由上而下层层剖析细说PCI+ExpresS+11新版精髓
- ul li 水平居中
- java语言的各种输入情况-ACM
- 零基础快速入门SpringBoot2.0教程 （二）
- POJ3694 Network 边双缩点+LCA+并查集