CF1982C Boring Day

原题链接：C. Boring Day

Tag：模拟

题目描述

你有 \(n\) 张顺序不能变的扑克牌， 给定你一个区间 \(l\)、\(r\)。 要求你按顺序取这些扑克牌， 你可以选择在抽到任意数字的牌之后结束这一回合。 回合结算的规则是只要你的点数之和在这个闭区间内， 就能够得一分，问最后能得多少分。

数据说明：

\(1 \le n \le 10^{5}\), \(1 \le l \le r \le 10^9, 1 \le a_i \le 10^9\)

分析

首先会有一种很容易想到的，并且也很容易想到这样是错的的贪心思路， 就是我们从第一个开始拿，每次拿到综合在目标区间内就结算一次，然后再开始拿, 一旦加爆了就直接结算开始下一轮。

这个错误贪心的反例很好想， 我们只要在这个错误的贪心上稍加修改就能够通过这道题。

因为错误的贪心思路是只要加爆了就直接结算，因为当前取的这张牌太大了。 但是这张牌不一定是没有用的，我们可以先判断一下这张牌单独拿出来是不是在目标区间内的。 如果在目标区间内，这张牌自己就可以结算一次了。 如果比目标区间大，那就没办法了，确实是要爆掉的。 如果比目标区间小，那我们就可以尝试让这个数字带上前面的数字看会不会爆。

说了这么多本质就是一个滑动窗口的思想。

写个 \(\text{deque}\) 模拟一下， 特判一下总值爆了的时候当前值能不能自己进行一次结算得分就可以了。

代码实现

void NeverSayNever() {
    int n,l,r; cin >> n >> l >>r;
    vector<int> vec(n);
    for(auto &x : vec) cin >> x;
    int sum = 0;
    int ans = 0;
    deque<int> dq;
    for(auto &x : vec){
        if(l <= x && x <= r){
            ans++;
            sum = 0;
            while(dq.size()){
                dq.pop_back();
            }
            continue;
        }
        while(dq.size() && sum + x > r){
            sum -= dq.front();
            dq.pop_front();
        }
        sum += x;
        dq.push_back(x);
        if(l <= sum && sum <= r){
            ans++;
            sum = 0;
            while(dq.size()){
                dq.pop_back();
            }
        }
    }
    cout << ans << endl;
}

额外思考

感觉是很简单的贪心，说实话没什么营养。

日志

本页面创建于 2024/6/26 02:16