题解：CF2068C Ads

ryan_yao · 2026-01-24 23:39:49 · 题解

思路

算法：贪心

每次找三个一组。

第一个视频的时间是剩下视频中时间最少的，设它为 x 分钟。

第二个视频的时间就设它为 y 分钟，那么前两个视频的时间和越靠近 k 越好。即 x + y < k。可以用 lowerbound 做。

第三个视频的时间越长越好，拖到每 3 个视频的广告。

最后注意一下一些细节就好了。

代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int t, n, k, d[N], ans;
vector<int> vec;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        vec.clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &d[i]);
            vec.push_back(d[i]);
        }

        sort(vec.begin(), vec.end());
        ans = 0;
        while (!vec.empty()) {
            ++ans;
            int x = vec[0];
            vec.erase(vec.begin());
            if (vec.empty()) break;
            if (x >= k) {
                continue;
            }
            auto it = lower_bound(vec.begin(), vec.end(), k - x);
            if (it != vec.begin()) {
                --it;
                vec.erase(it);
            }
            if (vec.empty()) break;
            vec.erase(prev(vec.end()));
        }

        printf("%d\n", ans - 1);
    }

    return 0;
}

谢谢