A. Increasing Sequence

题目连接：

http://www.codeforces.com/contest/11/problem/A

Description

A sequence a0, a1, ..., at - 1 is called increasing if ai - 1 < ai for each i: 0 < i < t.

You are given a sequence b0, b1, ..., bn - 1 and a positive integer d. In each move you may choose one element of the given sequence and add d to it. What is the least number of moves required to make the given sequence increasing?

Input

The first line of the input contains two integer numbers n and d (2 ≤ n ≤ 2000, 1 ≤ d ≤ 106). The second line contains space separated sequence b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106).

Output

Output the minimal number of moves needed to make the sequence increasing.

Sample Input

4 2
1 3 3 2

Sample Output

3

Hint

题意

你每次操作可以使得一个数增加d，问你最小操作多少次，可以使得这个序列变成一个递增序列

题解：

贪心就好了，能变就变，不用变的时候不变就好了

代码

#include<bits/stdc++.h> using namespace std; const int maxn = 2005; int a[maxn];int main() {int n,d;scanf("%d%d",&n,&d);for(int i=1;i<=n;i++)scanf("%d",&a[i]);long long ans = 0;for(int i=2;i<=n;i++)if(a[i]<=a[i-1]){int tmp = (a[i-1]-a[i]+d)/d;a[i]+=tmp*d;ans+=tmp;}cout<<ans<<endl; }

总结

以上是生活随笔为你收集整理的Codeforces Beta Round #11 A. Increasing Sequence 贪心的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。