Code+#2 火锅盛宴 - 算法竞赛题解 - 常规

[Code+#2] 火锅盛宴

题目背景

SkyDec 和 YJQQQAQ 都是 Yazid 的好朋友。他们都非常喜欢吃火锅。有一天，他们聚在一起，享受一场火锅盛宴。

题目描述

在这场火锅盛宴中，有一个麻辣浓汤锅底的火锅和 'n' 种食物，每种食物数量都是无限的。我们用 '1' 至 'n' 将这些食材编号。

每种食物煮熟所需要的时间不同，第 'i' 种食物煮熟需要 's_i' 单位时间。这表示如果你在第 'T' 个时刻将一个食物 'i' 下到火锅里，那么它会在第 'T+s_i' 个时刻被煮熟，并且此后一直会延续被煮熟的状态，直到它被拿走为止。

Yazid 和 YJQQQAQ 的口味不同：YJQQQAQ 觉得所有食物的好吃程度都是相同的；而 Yazid 则觉得没有两种食材的好吃程度是相同的，并且，巧合的是，编号越小的食物 Yazid 越喜欢吃。可怜的 SkyDec 由于不能吃辣，所以只能帮 Yazid 和 YJQQQAQ 煮食物。

整个火锅盛宴持续 '10^9' 单位时间。在整个盛宴中，三位好朋友除了谈笑风生之外，最重要的事当然就是吃东西了。在任意整数时刻，都有可能发生下列 '4' 种事件中的任意一种，我们用 '0' 至 '3' 之间的整数 'op' 描述事件类型：

'0 id'：表示 SkyDec 往火锅里下了一个编号为 'id' 的食物。
'1'：Yazid 在锅内搜寻熟了的且最喜欢吃的食物，并拿走一个这种食物。特别地，如果锅里没有熟了的食物，那么 Yazid 会很愤怒。
'2 id'：YJQQQAQ 在锅内搜寻编号为 'id' 的食物：
- 如果锅里不存在该种食物，则 YJQQQAQ 会很愤怒；
- 如果锅里存在熟了的该食物，则 YJQQQAQ 会取走一个并食用；
- 如果锅里只有未煮熟的该种食物，那么 YJQQQAQ 会希望知道最接近煮熟的该种食物（即锅内存在时间最长的该种食物）还需要多少时间被煮熟。
'3 l r'：馋涎欲滴的 SkyDec 想知道，锅里编号在 '[l,r]' 之间的且熟了的食物总共有多少个。

输入格式

从标准输入读入数据。

本题包含多组数据，输入的第一行为一个正整数 'T'，表示数据组数。接下来依次描述每组数据，对于每组数据：

第一行一个正整数 'n'，表示食物的种类数。

第二行 'n' 个用空格隔开的正整数 's_1,s_2,⋯, s_n'，描述每种食物煮熟需要的时间。

第三行一个正整数 'Q'，表示事件的数目。

接下来 'Q' 行，每行若干个用空格隔开的非负整数，描述一个事件。先是两个整数 't,op'，分别表示发生事件的时间以及事件的类型。

如果 'op=0' 或 'op=2'，则接下来 '1' 个正整数 'id'，意义见题目描述；
如果 'op=1'，则接下来没有其他数；
如果 'op=3'，则接下来 '2' 个正整数 'l,r'，意义见题目描述。

数据保证 't' 按输入顺序严格递增。

输出格式

对于每个 'op≠0' 的操作，输出一行表示答案。对于不同的 'op'，需要输出的内容如下：

对于 'op=1'，如果 Yazid 成功取走食物，则输出他取走食物的编号；否则输出 '‘Yazid is angry.’'（不含引号，下同）。
对于 'op=2'，如果 YJQQQAQ 成功取走食物，则输出 '‘Succeeded!’'；否则，如果锅里有未煮熟的该类食物，输出最接近煮熟的该种食物还需要多少时间被煮熟；否则，输出 '‘YJQQQAQ is angry.’'。
对于 'op=3'，输出锅内编号在指定范围内的熟食的数量。

样例 #1

样例输入 #1

样例输出 #1

Succeeded!
97
YJQQQAQ is angry.
2
1
2
Yazid is angry.

提示

对于所有数据，保证 'T≤4'，保证 'n≤100,000'，'Q≤500,000'，'1≤s_i≤10^8'，'1≤t≤10^9'，'op∈{0, 1, 2, 3}'，'1≤id≤n'，'1≤l≤r≤n'。数据保证 't' 按输入顺序严格递增。

来自 CodePlus 2017 12 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。

Credit：idea/王聿中命题/王聿中验题/吕时清，杨景钦

Git Repo：https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。

C++ 代码实现

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int maxN = 100010;
int n, Q, s[maxN];
deque<pii> q;
struct Node{
    int id, op;
    bool operator<(const Node &a)const{
        return id < a.id;
    }
}a[maxN];
int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1; i <= n; ++i)cin >> s[i];
        cin >> Q;
        q.clear();
        for(int i = 1; i <= Q; ++i){
            cin >> a[i].id >> a[i].op;
            if(a[i].op == 0 || a[i].op == 2)q.push_back(make_pair(i, a[i].id));
        }
        sort(q.begin(), q.end());
        int now = 0;
        for(auto i : q){
            if(now + s[i.second] <= a[i.first].id){
                now = a[i.first].id;
                a[i.first].op = -1;
            }
        }
        vector<int> ans;
        int cnt = 0;
        for(int i = 1; i <= Q; ++i){
            if(a[i].op == 1){
                if(cnt == 0){
                    ans.push_back(-1);
                }else{
                    ans.push_back(a[q[cnt-1].first].second);
                    --cnt;
                }
            }else if(a[i].op == 2){
                if(cnt == 0){
                    ans.push_back(-1);
                }else{
                    auto it = lower_bound(q.begin(), q.end(), make_pair(i, a[i].id));
                    if(it == q.end() || it->second != a[i].id){
                        ans.push_back(a[q[cnt-1].first].first-a[i].id);
                    }else{
                        ans.push_back(-1);
                        q.erase(it);
                        --cnt;
                    }
                }
            }else if(a[i].op == 3){
                int l = a[i].id, r = n;
                if(cnt){
                    l = max(l, a[q[cnt-1].first].first);
                }
                int res = r-l+1;
                ans.push_back(res);
            }else{
                ++cnt;
            }
        }
        for(auto i : ans){
            cout << i << endl;
        }
    }
    return 0;
}