AtCoder题解｜ABC 123B Five Dishes

题目信息 📚

【题目描述】

The restaurant AtCoder serves the following five dishes:

ABC Don (rice bowl): takes $A$ minutes to serve.
ARC Curry: takes $B$ minutes to serve.
AGC Pasta: takes $C$ minutes to serve.
APC Ramen: takes $D$ minutes to serve.
ATC Hanbagu (hamburger patty): takes $E$ minutes to serve.

Here, the time to serve a dish is the time between when an order is placed and when the dish is delivered.

This restaurant has the following rules on orders:

An order can only be placed at a time that is a multiple of $10$ (time $0$, $10$, $20$, …).
Only one dish can be ordered at a time.
No new order can be placed when an order is already placed and the dish is still not delivered, but a new order can be placed at the exact time when the dish is delivered.

E869120 arrives at this restaurant at time $0$. He will order all five dishes. Find the earliest possible time for the last dish to be delivered.

Here, he can order the dishes in any order he likes, and he can place an order already at time $0$.

【输入】

The input is given from Standard Input in the following format:

$A$
$B$
$C$
$D$
$E$

【输出】

Print the earliest possible time for the last dish to be delivered, as an integer.

【数据范围】

$A$, $B$, $C$, $D$ and $E$ are integers between $1$ and $123$ (inclusive).

【输入样例1】

【输出样例1】

If we decide to order the dishes in the order ABC Don, ARC Curry, AGC Pasta, ATC Hanbagu, APC Ramen, the earliest possible time for each order is as follows:

Order ABC Don at time $0$, which will be delivered at time $29$.
Order ARC Curry at time $30$, which will be delivered at time $50$.
Order AGC Pasta at time $50$, which will be delivered at time $57$.
Order ATC Hanbagu at time $60$, which will be delivered at time $180$.
Order APC Ramen at time $180$, which will be delivered at time $215$.

There is no way to order the dishes in which the last dish will be delivered earlier than this.

【输入样例2】

【输出样例2】

If we decide to order the dishes in the order AGC Pasta, ARC Curry, ATC Hanbagu, APC Ramen, ABC Don, the earliest possible time for each order is as follows:

Order AGC Pasta at time $0$, which will be delivered at time $119$.
Order ARC Curry at time $120$, which will be delivered at time $206$.
Order ATC Hanbagu at time $210$, which will be delivered at time $267$.
Order APC Ramen at time $270$, which will be delivered at time $378$.
Order ABC Don at time $380$, which will be delivered at time $481$.

There is no way to order the dishes in which the last dish will be delivered earlier than this.

【输入样例3】

【输出样例3】

Note that the input or output may not fit into a $32$-bit integer type.

【题目来源】

https://atcoder.jp/contests/abc123/tasks/abc123_b

题目解析 🍉

【题目分析】

法一：$5!$ 数据很小，利用 next_permutation() 无脑枚举所有排列。

法二：贪心，选个位数最小（此题最小为1）的放在最后即可。

【C++代码】全排列 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int a[10], p[10];

int main() {
    for (int i = 1; i <= 5; i++) cin >> a[i];

    // 全排列次序
    for (int i = 1; i <= 5; i++) p[i] = i;
    // 枚举所有排列，得到答案
    int ans = INT_MAX;
    do {
        int cur = 0;
        for (int i = 1; i <= 5; i++) {
            if (cur % 10) cur = cur + 10 - cur % 10;
            cur = cur + a[p[i]];
        }
        ans = min(cur, ans);
    } while (next_permutation(p + 1, p + 5 + 1));

    cout << ans << endl;
    return 0;
}

【C++代码】贪心 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int a[10];

int main() {
    for (int i = 1; i <= 5; i++) cin >> a[i];

    int sum = 0;
    int last_digit = INT_MAX;
    bool flag = false; // 判断数组中是否存在至少一个数的个位不是0
    for (int i = 1; i <= 5; i++) {
        sum += (a[i] + 9) / 10 * 10;  // 类向上取整
        if (a[i] % 10 > 0) {
            flag = true;
            last_digit = min(last_digit, a[i] % 10);
        }
    }
    // 输出答案
    if (flag) cout << sum - (10 - last_digit) << endl;
    else cout << sum << endl;

    return 0;
}