贪心 + 概率 – Blow up the Enemy – HDU 6803
2020 Multi-University Training Contest 4

题意：

$\mathrm{给}\mathrm{定}\mathrm{有}n\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{每}\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{有}2\mathrm{种}\mathrm{属}\mathrm{性}\mathrm{：}\mathrm{伤}\mathrm{害}{A}_i\mathrm{和}\mathrm{冷}\mathrm{却}\mathrm{时}\mathrm{间}{D}_i\mathrm{，}$

给定有n种武器，每种武器有2种属性：伤害Ai​和冷却时间Di​，

$\mathrm{张}\mathrm{三}\mathrm{和}\mathrm{爸}\mathrm{爸}\mathrm{各}\mathrm{从}n\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{种}\mathrm{选}\mathrm{择}\mathrm{一}\mathrm{个}\mathrm{武}\mathrm{器}\mathrm{进}\mathrm{行}\mathrm{对}\mathrm{战}\mathrm{。}$

张三和爸爸各从n种武器种选择一个武器进行对战。

$\mathrm{每}\mathrm{人}\mathrm{初}\mathrm{始}HP=100\mathrm{，}\mathrm{每}\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{每}\mathrm{次}\mathrm{攻}\mathrm{击}\mathrm{可}\mathrm{以}\mathrm{使}\mathrm{得}\mathrm{对}\mathrm{手}HP\mathrm{值}\mathrm{减}\mathrm{去}{A}_i\mathrm{，}HP\le 0\mathrm{的}\mathrm{一}\mathrm{方}\mathrm{出}\mathrm{局}\mathrm{。}$

每人初始HP=100，每种武器每次攻击可以使得对手HP值减去Ai​，HP≤0的一方出局。

$\mathrm{初}\mathrm{始}\mathrm{时}\mathrm{武}\mathrm{器}\mathrm{未}\mathrm{冷}\mathrm{却}\mathrm{，}\mathrm{每}\mathrm{攻}\mathrm{击}\mathrm{一}\mathrm{次}\mathrm{，}\mathrm{武}\mathrm{器}\mathrm{冷}\mathrm{却}{D}_i\mathrm{时}\mathrm{长}\mathrm{，}{D}_i\mathrm{时}\mathrm{间}\mathrm{后}\mathrm{，}\mathrm{可}\mathrm{立}\mathrm{刻}\mathrm{攻}\mathrm{击}\mathrm{。}$

初始时武器未冷却，每攻击一次，武器冷却Di​时长，Di​时间后，可立刻攻击。

$\mathrm{爸}\mathrm{爸}\mathrm{每}\mathrm{次}\mathrm{从}n\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{种}\mathrm{等}\mathrm{概}\mathrm{率}\mathrm{地}\mathrm{随}\mathrm{机}\mathrm{选}\mathrm{择}\mathrm{一}\mathrm{种}\mathrm{武}\mathrm{器}\mathrm{，}$

爸爸每次从n种武器种等概率地随机选择一种武器，

$\mathrm{若}\mathrm{二}\mathrm{人}\mathrm{的}HP\mathrm{同}\mathrm{时}\mathrm{小}\mathrm{于}\mathrm{等}\mathrm{于}0\mathrm{，}\mathrm{那}\mathrm{么}\mathrm{二}\mathrm{人}\mathrm{各}\mathrm{有}0.5\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{获}\mathrm{胜}\mathrm{。}$

若二人的HP同时小于等于0，那么二人各有0.5的概率获胜。

$\mathrm{请}\mathrm{帮}\mathrm{助}\mathrm{张}\mathrm{三}\mathrm{选}\mathrm{择}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{使}\mathrm{得}\mathrm{他}\mathrm{能}\mathrm{够}\mathrm{以}\mathrm{最}\mathrm{大}\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{获}\mathrm{胜}\mathrm{。}$

请帮助张三选择武器，使得他能够以最大的概率获胜。

输入：

$T\mathrm{组}\mathrm{测}\mathrm{试}\mathrm{数}\mathrm{据}\mathrm{，}$

T组测试数据，

$\mathrm{每}\mathrm{组}\mathrm{首}\mathrm{行}\mathrm{包}\mathrm{括}\mathrm{一}\mathrm{个}\mathrm{正}\mathrm{整}\mathrm{数}n\mathrm{，}\mathrm{表}\mathrm{示}\mathrm{武}\mathrm{器}\mathrm{的}\mathrm{种}\mathrm{类}\mathrm{。}$

每组首行包括一个正整数n，表示武器的种类。

$\mathrm{接}\mathrm{着}n\mathrm{行}\mathrm{输}\mathrm{入}n\mathrm{个}\mathrm{武}\mathrm{器}\mathrm{的}\mathrm{属}\mathrm{性}\mathrm{：}{A}_i\mathrm{和}{D}_i\mathrm{。}$

接着n行输入n个武器的属性：Ai​和Di​。

输出：

$\mathrm{张}\mathrm{三}\mathrm{获}\mathrm{胜}\mathrm{的}\mathrm{最}\mathrm{大}\mathrm{概}\mathrm{率}\mathrm{。}$

张三获胜的最大概率。

Sample Input

2

1

100 100

4

50 50

40 20

30 10

20 100


Sample Output
0.5

0.875


数据范围:
$1\le T\le 100\mathrm{，}1\le n\le 1000\mathrm{，}1\le A_i\le 100\mathrm{，}1\le D_i\le 10000$
1≤T≤100，1≤n≤1000，1≤Ai​≤100，1≤Di​≤10000
分析：
如何选择最优的武器？
$\mathrm{单}\mathrm{位}\mathrm{时}\mathrm{间}\mathrm{内}\mathrm{的}\mathrm{伤}\mathrm{害}\mathrm{似}\mathrm{乎}\mathrm{可}\mathrm{以}\mathrm{作}\mathrm{为}\mathrm{选}\mathrm{择}\mathrm{依}\mathrm{据}\mathrm{，}\mathrm{但}\mathrm{仔}\mathrm{细}\mathrm{考}\mathrm{虑}\mathrm{，}\mathrm{发}\mathrm{现}\mathrm{这}\mathrm{样}\mathrm{的}\mathrm{贪}\mathrm{心}\mathrm{策}\mathrm{略}\mathrm{是}\mathrm{错}\mathrm{的}\mathrm{。}$
单位时间内的伤害似乎可以作为选择依据，但仔细考虑，发现这样的贪心策略是错的。
$\mathrm{因}\mathrm{为}HP\mathrm{初}\mathrm{始}\mathrm{值}\mathrm{是}\mathrm{确}\mathrm{定}\mathrm{的}\mathrm{，}\mathrm{武}\mathrm{器}\mathrm{每}\mathrm{次}\mathrm{的}\mathrm{伤}\mathrm{害}\mathrm{和}\mathrm{冷}\mathrm{却}\mathrm{时}\mathrm{间}\mathrm{也}\mathrm{是}\mathrm{确}\mathrm{定}\mathrm{的}\mathrm{，}$
因为HP初始值是确定的，武器每次的伤害和冷却时间也是确定的，
$\mathrm{那}\mathrm{么}\mathrm{对}\mathrm{于}\mathrm{每}\mathrm{个}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{就}\mathrm{能}\mathrm{够}\mathrm{计}\mathrm{算}\mathrm{出}\mathrm{使}\mathrm{用}\mathrm{该}\mathrm{武}\mathrm{器}\mathrm{击}\mathrm{败}\mathrm{对}\mathrm{手}\mathrm{的}\mathrm{时}\mathrm{间}Time\mathrm{。}$
那么对于每个武器，就能够计算出使用该武器击败对手的时间Time。
$Time=(\mathrm{攻}\mathrm{击}\mathrm{次}\mathrm{数}-1)\times \mathrm{冷}\mathrm{却}\mathrm{时}\mathrm{间}$
Time=(攻击次数−1)×冷却时间
$\mathrm{攻}\mathrm{击}\mathrm{次}\mathrm{数}=\lceil \frac{100}{A_i}\rceil \mathrm{，}\mathrm{故}Time=(\lceil \frac{100}{A_i}\rceil -1)\times D_i$
攻击次数=⌈Ai​100​⌉，故Time=(⌈Ai​100​⌉−1)×Di​
$\mathrm{那}\mathrm{么}Time\mathrm{最}\mathrm{小}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{就}\mathrm{是}\mathrm{最}\mathrm{优}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{记}\mathrm{所}\mathrm{有}\mathrm{武}\mathrm{器}\mathrm{中}\mathrm{的}\mathrm{最}\mathrm{小}Time\mathrm{为}mint\mathrm{，}$
那么Time最小的武器就是最优的武器，记所有武器中的最小Time为mint，
$\mathrm{注}\mathrm{意}\mathrm{，}\mathrm{可}\mathrm{能}\mathrm{有}\mathrm{多}\mathrm{个}\mathrm{武}\mathrm{器}\mathrm{的}Time=mint\mathrm{，}\mathrm{假}\mathrm{设}\mathrm{有}cnt\mathrm{个}\mathrm{武}\mathrm{器}\mathrm{的}Time=mint\mathrm{，}$
注意，可能有多个武器的Time=mint，假设有cnt个武器的Time=mint，
$\mathrm{那}\mathrm{么}\mathrm{，}\mathrm{张}\mathrm{三}\mathrm{获}\mathrm{胜}\mathrm{的}\mathrm{概}\mathrm{率}=1-\mathrm{张}\mathrm{三}\mathrm{失}\mathrm{败}\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{，}$
那么，张三获胜的概率=1−张三失败的概率，
$\mathrm{要}\mathrm{使}\mathrm{得}\mathrm{张}\mathrm{三}\mathrm{获}\mathrm{胜}\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{最}\mathrm{大}\mathrm{，}\mathrm{那}\mathrm{么}\mathrm{张}\mathrm{三}\mathrm{必}\mathrm{选}\mathrm{择}\mathrm{最}\mathrm{优}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{，}$
要使得张三获胜的概率最大，那么张三必选择最优的武器，
$\mathrm{①}\mathrm{、}\mathrm{若}\mathrm{爸}\mathrm{爸}\mathrm{选}\mathrm{择}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{不}\mathrm{是}\mathrm{最}\mathrm{优}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{那}\mathrm{么}\mathrm{张}\mathrm{三}\mathrm{必}\mathrm{胜}\mathrm{。}$
①、若爸爸选择的武器不是最优的武器，那么张三必胜。
$\mathrm{②}\mathrm{、}\mathrm{若}\mathrm{爸}\mathrm{爸}\mathrm{选}\mathrm{择}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{是}\mathrm{最}\mathrm{优}\mathrm{的}\mathrm{武}\mathrm{器}\mathrm{，}\mathrm{那}\mathrm{么}\mathrm{张}\mathrm{三}\mathrm{有}0.5\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{失}\mathrm{败}\mathrm{。}$
②、若爸爸选择的武器是最优的武器，那么张三有0.5的概率失败。
$\mathrm{因}\mathrm{此}\mathrm{，}\mathrm{张}\mathrm{三}\mathrm{失}\mathrm{败}\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{即}\mathrm{爸}\mathrm{爸}\mathrm{获}\mathrm{胜}\mathrm{的}\mathrm{概}\mathrm{率}\mathrm{，}\mathrm{为}\frac{cnt}{n}\times 0.5\mathrm{，}$
因此，张三失败的概率即爸爸获胜的概率，为ncnt​×0.5，
$\mathrm{故}\mathrm{最}\mathrm{终}\mathrm{答}\mathrm{案}\mathrm{为}\mathrm{：}1-\frac{cnt}{n}\times 0.5$
故最终答案为：1−ncnt​×0.5
代码：
#include<cstring>

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;
const int N=1010;
int T,n;

struct weapons

{

    int a,d;

    int Time;

}w[N];
int main()

{

    scanf("%d",&T);

    while(T--)

    {

        cin>>n;

        int cnt=0, mint=1e6;

        for(int i=0;i<n;i++)

        {

            int a,d,t;

            cin>>a>>d;

            t=((100+a-1)/a-1)*d;

            w[i]={a,d,t};

            mint=min(t,mint);

        }

        for(int i=0;i<n;i++) if(w[i].Time==mint) cnt++;
        double ans=1-(double)cnt/n*0.5;

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

    }
    return 0;

}


原创：https://www.panoramacn.com

源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。
专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说


免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。
您必须遵守我们的协议，如果您下载了该资源行为将被视为对《免责声明》全部内容的认可->
联系客服
投诉资源
 www.panoramacn.com资源全部来自互联网收集，仅供用于学习和交流，请勿用于商业用途。如有侵权、不妥之处，请联系站长并出示版权证明以便删除。
敬请谅解！ 侵权删帖/违法举报/投稿等事物联系邮箱：2640602276@qq.com
                
                
未经允许不得转载：书荒源码源码网每日更新网站源码模板！ » 贪心 + 概率 – Blow up the Enemy – HDU 6803
                                
                                    
贪心 + 概率 - Blow up the Enemy - HDU 6803
                                
                    

        

            
            
关注我们小说电影免费看
            
关注我们，获取更多的全网素材资源，有趣有料！
            
120000+人已关注
        
    
 
                
                    


                    
分享到：
        
                                赞(0)
        
                    打赏