自动搬运

查看原文

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 22:45:34，当前版本为作者最后更新于2023-03-11 16:22:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}