题解：CF248D Sweets for Everyone!

Chaniaq_awa · 2025-03-08 19:59:27 · 题解

在这里讲一下我对这道题的理解:

先讲一下这题的过程，再详细解释一下各部分： 二分开始手里拿的糖，验证时就是贪心，取能发完糖的最少时间然后和题目给的比大小。

首先，为什么是二分，因为开始拿的糖满足单调性，也就是开始糖拿的越多成功的可能越大，所以显而易见是二分

然后思考贪心策略，我们分成两个思路来想：

• 手里还有糖，那肯定给出去
• 手里没有糖，那这时候我们可以想到一种策略，就是经过房子的时候先欠着糖，等手里有足够的糖了的一瞬间再还回去。那么我们想，怎么证明这样是对的呢，因为如果我们继续往前走，往前走没有拿到任何糖然后再折返，那么肯定是会比刚刚那种策略差的。那我们再思考，如果往前拿到了糖呢？仔细思考可以知道，第一种策略不会比继续往前更差。如果我们还糖那么从你现在拿完糖了到欠糖的那一步需要往返，也就是这段路程走了两次，然后就可以继续走了。那如果我们继续往前走呢，那和这个策略一样，都是一段路程走了两次。所以证明这种策略是最优的。

这时候代码就很容易写了，细节都在代码里了

#include <bits/stdc++.h>
using namespace std;
int n,t;
string s;
int sum;
bool check(int x) { //x为带的糖数  
    int num_H = 0;      // 已收集的H数量
    int fir = 0;     // 第一个未处理的H的位置
    int las = 0;     // 最后一个未处理的H的位置
    int cnt = 0;      // 需要额外往返的时间
    int lt = t;        // 剩余时间
    for(int i = 1;i <= n;i++) {
        if (num_H == sum && x >= 0)
            return lt >= min(i - fir, cnt);
        lt--; // 移动一步消耗时间
        if(s[i] == 'H') {
            if(!x) {
                if(!fir) fir = i;
                las = i;
            }
            x--;
            num_H++;
        }
        else if (s[i] == 'S') {
            x++;
            if (!x) {
                cnt += i - las; //不会有比这更优的策略 
                if (num_H != sum) cnt += i - las; // 往返路径
            }
        }
    }
    return lt >= min(n - fir, cnt) && x >= 0;
}
int main() {
    cin >> n >> t; cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
        sum += (s[i] == 'H');
    int l = 0,r = sum;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if(check(l)) cout << l << endl;
    else cout << -1;
    return 0;
}