CodeForces - 11A Increasing Sequence

4959 단어 codeforces수제
[제목 설명] A sequence a0,   a1,  ...,   at   -   1 is called increasing if ai   -   1  
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?
【입력】 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 the minimal number of moves needed to make the sequence increasing.
[샘플 입력] 4, 2, 1, 3, 2.
[샘플 출력] 3
제목 링크:https://codeforces.com/contest/11/problem/A
원래의 수열에서, 몇몇 숫자에 d를 몇 번 더해서 점차적으로 증가시키고, 최소 횟수를 구한다
코드는 다음과 같습니다.
#include 
using namespace std;
static const int MAXN=2000+10;
int a[MAXN];
int n,d;
int main()
{
     
    cin>>n>>d;
    for(int i=0;i<n;i++) cin>>a[i];
    int cnt=0;
    for(int i=1;i<n;i++)
    {
     
        if(a[i]>a[i-1]) continue;
        int t=(a[i-1]+d-a[i])/d;
        cnt+=t;
        a[i]+=d*t;
    }
    cout<<cnt<<endl;
    return 0;
}

좋은 웹페이지 즐겨찾기