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

題意

你每次操作可以使得一個數(shù)增加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; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Beta Round #11 A. Increasing Sequence 贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。