Watching Mooloo (USACO Bronze 2023 February)

B牛要看网络视频（Mooloo是牛版Hulu的谐音），给定 $N$ 个不同的要看的日子，以及连续订阅 $d$ 天的费用 $d+K$ （ $K$ 为常数），问最少花多少钱。

直观理解，如果连续一段时间看较多电视，那么应该连续订阅，这样可以“摊薄” $K$ 这个固定费用。而如果好长一段时间不看，就应该取消订阅，等需要看的时候再恢复。

这个直觉引导我们关注两次观看之间间隔的天数，这个是否直接能决定我们是否要中断订阅呢？答案是肯定的，如果我们中断，那么可以认为下一次观看就要额外付费 $K$ 元。而如果继续订阅，那么虽然不需要付固定费用，但是就需要额外付中间的间隔天数的费用。

所以我们就能得到一个贪心的策略，就是在每次观看之后，看下一次观看的间隔，如果小于 $K$ ，那么继续订阅，否则中断订阅。这样一步步走下去，就能得到最优解。

复杂度是 $\mathcal{O}(N)$ 。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, K;   // n <= 1e5, K <= 1e9
ll d[100005];   // 1e14
ll ans;
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 0; i < n; i++)
        scanf("%lld", &d[i]);
    
    ans = K;
    for (int  i = 0; i < n; i++) {
        int dist = i < n-1 ? d[i+1] - d[i] : 1;
        if (dist <= K)      // greedy：如果见隔大于K，就中断订阅
            ans += dist;
        else
            ans += K+1;
    }
    printf("%lld", ans);
    return 0;
}