Bessie likes to watch Mooloo's shows. Because Bessie is a busy cow, she has planned a schedule for the next N(1≤N≤10^5) days in which she will watch Mooloo. Because Mooloo is a paid subscription service, she now needs to decide how to minimize the amount she needs to pay.
Mooloo has an interesting subscription system: it costs d+K(1≤K≤10^9) to subscribe to Mooloo for d days in a row. You can start a subscription at any time, and if the current subscription expires, you can start a new subscription as many times as you need. With this in mind, calculate the minimum amount Bessie will need to pay in order to complete her plan.
INPUT FORMAT(input from terminal /stdin) :
The first line contains the integers N and K.
The second line contains N integers describing the number of days Bessie watched Mooloo: 1≤d1< d2< ... < dN≤10^14.
OUTPUT FORMAT(to print the output to terminal/standard output) :
Note that large integer sizes involved in this question may require the use of 64-bit integer data types(for example, "long-long" in C/C++).
Sample input:
2 4
7 9
Sample output:
7.
Bessie bought a three-day subscription on day 7, costing d+K=3+4=7 yuan.
Sample input:
2 3
1 10
Sample output:
8.
The first day Bessie bought a one-day subscription, it cost d+K=1+3=4 yuan. Bessie also bought a one-day subscription on day 10, which cost d+K=1+3=4 yuan. Bessie spent a total of 8 yuan.
Score:
Input 3-5:N≤10
Input 6-12: No additional restrictions.
This is the topic assigned by the school today, I do not know, I hope you can help to answer it(using C++ algorithm), the most hope to give the code and ideas!
0 Answer
No answer yet
这家伙很懒，什么都没留下...