codeforce 11 A

78 阅读 0 评论 52 点赞

我是靠谱客的博主霸气秀发，这篇文章主要介绍codeforce 11 A，现在分享给大家，希望可以做个参考。

http://vjudge.net/contest/view.action?cid=18290#problem/A

Description

A sequence a₀, a₁, ..., a_t - 1 is called increasing if a_i - 1 < a_i for each i: 0 < i < t.

You are given a sequence b₀, b₁, ..., b_n - 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 ≤ 10⁶). The second line contains space separated sequence b₀, b₁, ..., b_n - 1 (1 ≤ b_i ≤ 10⁶).

Output

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

Sample Input

Input

复制代码

Output

复制代码

1
3

一不小心就超时。。。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int a[10005];
int main()
{
    int n,d;
    while(~scanf("%d%d",&n,&d))
    {
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        int sum=0;
        for(int i=1; i<n; i++)
        {
            if(a[i]<=a[i-1])
            {
                int x=a[i-1]-a[i];
                a[i]+=(x/d)*d;
                sum+=x/d;
                if(a[i]<=a[i-1])
                {
                    a[i]+=d;
                    sum++;
                }
                if(a[i]<=a[i-1])
                {
                    a[i]+=d;
                    sum++;
                }
            }
        }
        printf("%dn",sum);
    }
    return 0;
}