长春理工大学第十四届程序设计竞赛（重现赛）I.Fate Grand Order

链接：https://ac.nowcoder.com/acm/contest/912/I

题意：

Fate Grand Order是型月社发行的角色扮演类手机游戏，是著名的氪金抽卡"垃圾"手游。

小t是该手游的忠实厨力玩家，为了抽到喜欢的角色他特地氪金买了n颗圣晶石(3颗圣晶石可以抽卡1次)。

已知有m个抽卡活动会按时间顺序在游戏中举办，每个活动都会新推出一个角色，并且告诉你这m个角色的抽取概率，而每当首次成功抽到每个角色之后他会获得一定的开心值。

小t是一个有计划的男人，在第1个活动开始前他就会想好一个抽卡计划，抽卡计划决定哪些角色抽，哪些角色不抽；

小t也是一个贫穷的男人，对于每个选择抽卡的活动，他都只会抽一次，不管是否抽到都不会选择继续再在这个活动抽卡；

小t也是一个纠结的男人，每个角色他都很纠结是否要抽，总之他想让自己尽可能开心，所以小t求助于聪明的你，他想知道什么样的计划可以让开心值的期望最大。

思路：

根据概率和开心值的乘积排序。

取前n/3个。

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3+10;

struct Node

{

    double p;

    double happy;

    int pos;

    bool operator < (const Node& that) const

    {

        return this->p*this->happy > that.p*that.happy;

    }

}node[MAXN];

int Vis[MAXN];

int main()

{

    int n, m;

    cin >> n >> m;

    n = n/3;

    for (int i = 1;i <= m;i++)

        cin >> node[i].p, node[i].pos = i;

    for (int i = 1;i <= m;i++)

        cin >> node[i].happy;

    sort(node+1, node+1+m);

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

        Vis[node[i].pos] = 1;

    for (int i = 1;i <= m;i++)

        if (Vis[i] == 0)

            cout << 0;

        else

            cout << 1;

    cout << endl;

    return 0;

}

巴特西

长春理工大学第十四届程序设计竞赛（重现赛）I.Fate Grand Order

链接：https://ac.nowcoder.com/acm/contest/912/I

题意：

思路：

代码：

最新文章

热门文章