2021TX开发第三次笔试题之一:游戏俱乐部

题目概述

游戏俱乐部,正如其名,是一个由数个网络游戏构成的俱乐部,当玩家进入俱乐部时,会得到一张游戏清单,列举了俱乐部内今日开放的n个小游戏,其中第i个小游戏必须在时刻内完成(假设玩家进入俱乐部时为0时刻,开始玩某一游戏时只需要一个单位时间即可完成,不计阅读游戏清单以及俱乐部路上行走时间),否则,就会扣除点荣耀积分。

每天,俱乐部都会向最优顺序选择者授予纪念勋章,所谓的最优顺序,即:最终扣除的积分最少的玩家。

小明十分想要一枚纪念勋章,那么该怎么设计最优顺序呢?

输入输出描述:

本题为多组测试数据,第一行输入一个正整数T(1 <= T <= 1000),代表测试数据组数;
对于每组数据,第一行输入一个正整数n(1 <= n <= 1000),代表今天开放的游戏数。
 
示例1:
 
输入:
1
3
3 1 1
3 6 9
 
输出:
6
 
说明:
首先完成游戏 3,此时,游戏 2未在规定时间内完成,扣除6分;接着只需要在时刻 3之前完成游戏 1即可。
这种安排方案,只需要被扣除6分。

解题思路
首先我想到的大致思路有两个,一个是贪心,一个是动态规划。先考虑动态规划,也就是说能不能构建最优子问题。我发现,这似乎不太现实。。。比如下面的例子1:

1
4
1 3   3  2
5 100 10 1

假设我们用一维dp,构建的子问题是说,在前i个单位时间内最优排序情况下最小的扣除分是dp[i]。可以看到,dp[1] = 0,就是只玩第一个游戏;dp[2] = 0,就是第一个单位时间玩第一个游戏,第二个单位时间玩第二个游戏;dp[3] = 1,就是第一个单位时间玩第一个,第二、三个单位时间分别玩第三、四个游戏,不玩第二个游戏。这样的话,dp[3]并没有包含dp[2]和dp[1],也就是说,我们这样构建的dp是有问题的。

接着我就想,能不能通过贪心的方法来解决问题。一开始的解决思路是:先按照时间顺序从小到大排序、再按照扣分代价从大到小排序,然后依次选取排序好的游戏即可。这个做法的问题是,如果后面有代价很大的游戏的话,我们只顾着眼前的要完结的游戏,却没能考虑之后的游戏,会造成总代价很大(比如上面的例子1)。

既然正序的贪心走不通,我就倒序贪心一下。我们首先排序一下所有游戏的截止时间,找出最晚截止的,然后从后往前安排需要玩的游戏。在时刻,我们选择的游戏应当是可以最小化扣除荣耀积分的那个,也就是截止时间是的、扣分最多的游戏。以此类推,在第i个时刻,我们玩的游戏范围是:截止时间在第i个时刻到时刻的所有游戏(去除已经玩了的那些游戏)。也就是说,我们要动态地更新当前的待玩游戏列表中的游戏代价顺序,选出那个最大的。这里我采用了堆实现,可以达到O(n log(n))的时间复杂度。

算法性能
时间复杂度是O(n log(n)),空间复杂度是O(n)。

样例代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
 
#define NUM 1000
 
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first < b.first)
        return false;
    else if (a.first == b.first)
        return a.second < b.second;
    return true;
}
 
int main()
{
    int N, res;
    cin >> N;
    for (int ni = 0; ni < N; ++ni)
    {
        int Ng;
        res = 0;
        cin >> Ng;
        int *time_ddl = new int[Ng];
        int *time_pen = new int[Ng];
        for (int gi = 0; gi < Ng; ++gi)
            cin >> time_ddl[gi];
        for (int gi = 0; gi < Ng; ++gi)
        {
            cin >> time_pen[gi];
            res += time_pen[gi];
        }
 
        vector<pair<int, int>> time_sort;
        for (int gi = 0; gi < Ng; ++gi)
            time_sort.push_back(pair<int, int> {time_ddl[gi], time_pen[gi]});
        sort(time_sort.begin(), time_sort.end(), cmp);
 
        int pc = time_sort.front().first;
        priority_queue<int, vector<int>, less<int>> pen;
        for (auto idx = time_sort.begin(); idx != time_sort.end();)
        {
            if (pc == (*idx).first)
            {
                pen.push((*idx).second);
                idx++;
            }
            else
            {
                while (pc != (*idx).first)
                {
                    if (pen.empty() == 0)
                    {
                        res -= pen.top();
                        pen.pop();
                    }
                    pc--;
                }
            }
        }
        res -= pen.top();
 
        cout << res << endl;
 
        delete [] time_ddl;
        delete [] time_pen;
    }
}

评论

暂无评论