官方题解｜君往何处

题目解析

枚举；贪心

从小到大枚举使用的手指数量；

对于枚举的手指数量为 $X$，存储每个手指下一次可以点击音符的最早时间 $a_1, a_2, \cdots, a_X$，遍历所有的音符，对于每个到来的音符 $i$ 使用选择手指 $j$ 满足 $a_j = \min{(a_1, a_2, \cdot, a_X)}$，来尝试点击这个音符，并且尽可能早地点击这个音符，即 $\max{(a_j, t_i - 30)}$。这样我们便可以保证在使用 $X$ 个手指的情况下，使得每个音符都可以在允许的最早的时刻被点击。

时间复杂度 $\mathrm{O}(N)$。

AC代码

#include <bits/stdc++.h>
 
int solve() {
    int n; std::cin >> n;
    std::vector<int> t(n);
    for (auto &x : t) std::cin >> x;
    std::vector<int> a(4);
    auto check = [&](int m) {
        std::vector<int> a(m);
        for (auto &x : t) {
            auto it = std::min_element(a.begin(), a.end());
            if (*it > x + 30) return false;
            *it = std::max(*it, x - 30) + 100;
        }
        return true;
    };
    for (int i = 1; i <= 4; ++i) {
        if (check(i)) {
            std::cout << i << '\n';
            return 0;
        }
    }
    std::cout << -1 << '\n';
    return 0;
}
 
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}