C - Perform Easily

Description

Solution

对于每一个 $b_i$ ，将 $<b_i - a[j], i>(1 \le j \le 6)$ 求出并按第一关键字排序。

遍历排序后的二元组，对于当前二元组 $i$ ，向右找到第一个 $j$ 使得它们之间二元组的第二关键字有 $n$ 种，那么这样的 $i$ 、 $j$ 的第一关键字对应的区间可以被计入答案。

由于 $i$ 单增时 $j$ 也是单增的，故可用双指针扫描。判断第二关键字是否有 $n$ 种可用 map<int, int> cnt 获取 size() 来实现，当一个数的 $cnt$ 变为 0 时，将其从 $map$ 中 erase 即可 (似乎只用数组就够了)。

Code

Perform Easily

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, ans = 1e9;
array<int, 7> a;
array<int, MAXN> b;

vector<pair<int, int>> vec;
unordered_map<int, int> cnt;

int main() {
    boost;
    for (int i = 1; i <= 6; i++) cin >> a[i];
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        for (int j = 1; j <= 6; j++) vec.push_back({b[i] - a[j], i});
    }
    sort(vec.begin(), vec.end());

    int r = 0;
    for (int l = 0; l < vec.size(); l++) {
        if (cnt.size() < n && r + 1 == vec.size()) break;
        while (cnt.size() < n && r < vec.size()) {
            cnt[vec[r].second]++;
            r++;
        }

        if (cnt.size() == n)
            ans = min(ans, vec[r - 1].first - vec[l].first);

        cnt[vec[l].second]--;
        if (!cnt[vec[l].second]) cnt.erase(vec[l].second);
    }
    cout << ans << endl;
    return 0;
}

D - Shurikens

Description

题目链接

Solution

按事件发生的相反顺序考虑。由于每次拿走的 $shuriken$ 的价格是最小的，故遇到 ‘-’ 事件时，将对应价格插入 $MinHeap$ ；否则从 $MinHeap$ 中弹出堆顶元素并压入栈，那么剩下的元素一定在这个事件发生之前就有了。

不合法情况：当前事件为 ‘+’ 且堆为空；或者当前事件为 ‘-’，对应的价格大于堆顶元素 (也就是拿走的价格不是最小的)。

最后输出栈中元素即可。

Code

Shurikens

#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n, val[MAXN];
stack<int> ans;
char type[MAXN];
priority_queue<int, vector<int>, greater<int>> q;

int main() {
    boost;
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
       cin >> type[i];
       if (type[i] == '-') cin >> val[i];
    }

    for (int i = 2 * n; i; i--) {
        if (type[i] == '+') {
            if (q.empty()) {
                cout << "NO\n";
                return 0;
            }
            ans.push(q.top());
            q.pop();
        } else {
            if (q.empty()) {
                q.push(val[i]);
                continue;
            }
            if (val[i] > q.top()) {
                cout << "NO\n";
                return 0;
            }
            q.push(val[i]);
        }
    }
    cout << "YES\n";
    while (!ans.empty()) {
        cout << ans.top() << " ";
        ans.pop();
    }
    return 0;
}

E - Solo mid Oracle

Description

题目链接

Solution

首先如果 $a > b * c$ ，那么无论生命值为多少都可以击杀。

然后画图分析可得，设初始生命值为 $st$ ，第 $x$ 次使用技能，则使用技能时的血量为 $st - a * (x + 1) + x * (x + 1) / 2 * b * d$ 。

当 $x > \frac{c}{d}$ 时，不会出现比 $x <= \frac{c}{d}$ 中更小的结果。故只需考虑 $0 \le x \le \frac{c}{d}$ ，然后对单谷函数三分求极值即可。

Code

Solo mid Oracle

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int tc, a, b, c, d;

inline int f(int x) {
    return -a * (x + 1) + x * (x + 1) / 2 * b * d;
}

inline void tripartition() {
    int l = 0, r = c / d, ans = 1e18;
    while (r - l >= 3) {
        int lmid = (l + l + r) / 3;
        int rmid = (l + r + r) / 3;
        int lval = f(lmid), rval = f(rmid);
        if (lval < rval) r = rmid;
        else l = lmid;
    }
    for (int i = l; i <= r; i++) {
        ans = min(ans, f(i));
    }
    cout << -ans << "\n";
}

signed main() {
    boost;
    cin >> tc;
    while (tc--) {
        cin >> a >> b >> c >> d;
        if (a > b * c) cout << -1 << "\n";
        else tripartition();
    }
    return 0;
}