CodeForces-1113A Sasha and His Trip（贪心）

旧城等待， 2022-02-13 09:55 145阅读 0赞

**Problem Description:**

Sasha is a very happy guy, that's why he is always on the move. There are nn cities in the country where Sasha lives. They are all located on one straight line, and for convenience, they are numbered from 11 to nn in increasing order. The distance between any two adjacent cities is equal to 11 kilometer. Since all roads in the country are directed, it's possible to reach the city yy from the city xx only if x<yx<y.

Once Sasha decided to go on a trip around the country and to visit all nn cities. He will move with the help of his car, Cheetah-2677. The tank capacity of this model is vv liters, and it spends exactly 11 liter of fuel for 11 kilometer of the way. At the beginning of the journey, the tank is empty. Sasha is located in the city with the number 11 and wants to get to the city with the number nn. There is a gas station in each city. In the ii-th city, the price of 11 liter of fuel is ii dollars. It is obvious that at any moment of time, the tank can contain at most vv liters of fuel.

Sasha doesn't like to waste money, that's why he wants to know what is the minimum amount of money is needed to finish the trip if he can buy fuel in any city he wants. Help him to figure it out!

**Input:**

The first line contains two integers nn and vv (2≤n≤1002≤n≤100, 1≤v≤1001≤v≤100)  — the number of cities in the country and the capacity of the tank.

**Output:**

Print one integer — the minimum amount of money that is needed to finish the trip.

**Examples:**

Input

4 2

Output

Input

7 6

Output

**Note:**

In the first example, Sasha can buy 22 liters for 22 dollars (11 dollar per liter) in the first city, drive to the second city, spend 11 liter of fuel on it, then buy 11liter for 22 dollars in the second city and then drive to the 44-th city. Therefore, the answer is 1+1+2=41+1+2=4.

In the second example, the capacity of the tank allows to fill the tank completely in the first city, and drive to the last city without stops in other cities.

**题目大意：**

Sasha开车从1地走到n地，汽车行驶需要汽油，i地的汽油单价为i，x地与x+1地的距离是1公里，每公里消耗一个单位的汽油，Sasha最开始的时候在1地，Sasha的汽车油箱的容积为v，问Sasha从1地到n地最少需要多少油钱。

**思路：**

**尽量在靠近1地的加油站加油，因为靠近1地的加油站的汽油便宜，并且在需要的范围内能加多少油就加多少油。**

**上AC代码：**

#include <stdio.h>
    int n,v;
    int i;
    int main()
    {
        //油钱
        int cost=0;
        //剩余的油量
        int left=0;
        scanf("%d%d",&n,&v);
        for(i=1;i<=n;i++)
        {
            //油箱的容量小于需要的油量
            if(v<=n-i)
            {
                //此时应该加满
                cost+=(v-left)*i;
                left+=v-left;
            }
            //剩余的油量小于需要的油量
            else if(left<n-i)
            {
                //在需要的范围内能多加油就多加油
                cost+=(n-i-left)*i;
                left+=n-i-left;
            }
            //消耗汽油
            left--;
        }
        printf("%d\n",cost);
        return 0;
    }

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: /images/20220213/75147976e306446d898c277aa4e93323.png