P9123 [USACO23FEB] Watching Mooloo B 题解

· · 题解

题意：奶牛想看电视节目，这个电视节目支持两种充值方法：

  1. 订阅 vip，每次花费 k+1 元，能看 1 天。
  2. 续费，在已经订阅的情况下，花费 1 元，多看 1 天。

奶牛会在 d_i 天看一次，求最省钱的订阅方法。

思路：如果下一次看距离这一次看的天数大于 k，则重新订阅，否则就续费。

时间复杂度是 O(n)。

代码：

#include<iostream>
using namespace std;
long long n,k,a[100001],ans,tmp;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        tmp=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]-a[j-1]<=k){
                ans+=a[j]-a[j-1];
                tmp++;//如果续费是划算的
            }
            else break;//如果续费已经不再划算
        }
        ans++;
        ans+=k;
        i=tmp;
    }
    cout<<ans;
}