C-小明分蛋糕

C-小明分蛋糕

/ 0评 / 1294次 / 0

Description

小明分蛋糕,开始小明有a块蛋糕,经过分配后小明要拥有b块蛋糕,老师为了给小明增加难度,要求小明分蛋糕时只能采取以下6种操作:

(1)输入-5 表示丢掉5块蛋糕

(2)输入-2 表示丢掉2块蛋糕

(3)输入-1 表示丢掉1块蛋糕

(4)输入1 表示获得1块蛋糕

(5)输入2 表示获得2块蛋糕

(6)输入5 表示获得5块蛋糕

最后,老师要求小明回答:从a块蛋糕到b块蛋糕,所需的最少的步骤数为多少。

Input

第一行,输入t,表示有t组数据 (1≤t≤1000) 接下来,每组数据输入两个整数a,b(0≤a,b≤1e9)

Output

共t行,每行输出从a到b所需的最少步骤数(若a==b,则直接输出0)

Analysis

明显且简单的贪心题,题目说的很玄乎又是加啊减的,不妨请看,我如果是想实现+3块蛋糕,不管是+2+1还是+5-2都不可能比两步更少,+4块蛋糕也同理,也就意味着不存在需要额外考虑的更优解,那也就直接贪心粗暴解决即可

Accepted Code

/*
 * @Author: Gehrychiang
 * @LastEditors: Gehrychiang
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
//greedy
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    while (cin >> t)
    {
        while (t--)
        {
            int a, b;
            cin >> a >> b;
            if (a == b)
            {
                printf("0\n");
            }
            else
            {
                int cnt = 0;
                int dis = abs(a - b);
                while (dis / 5 > 0)// 5 prior
                {
                    cnt = cnt + (dis / 5);
                    dis = dis % 5;
                }
                while (dis / 2 > 0)
                {
                    cnt = cnt + (dis / 2);
                    dis = dis % 2;
                }
                while (dis / 1 > 0)
                {
                    cnt = cnt + (dis / 1);
                    dis = dis % 1;
                }
                printf("%d\n", cnt);
            }
        }
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63969