2024 小木棍 · 方案一先定位数再贪心

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1630 字

位数取最少，再逐位从 0 到 9 试

2024
贪心

正文

// CSP-J 2024 复赛 T3 · 小木棍
// 原题：https://oj.yecheng.tv/p/ccf-CSPJ2024C
// 题意：用火柴棒拼数字，各数字需要的根数是
//   0:6  1:2  2:5  3:5  4:4  5:5  6:6  7:3  8:7  9:6
// 要恰好用 n 根拼一个正整数、不能有前导零，并且这个数要尽可能小；做不到就输出 -1。
//
// 方案一 · 先定位数，再逐位贪心
// 第一步 定最少位数：每位最多用 7 根（数字 8），所以最少位数 len = ceil(n / 7)；
//   每位最少用 2 根（数字 1），所以如果 n < 2 * len 就无解（n = 1 就是这样被排除的）。
//   位数越少数值越小，所以位数一定取到最少。
// 第二步 逐位从 0 到 9 试：假设这一位用掉 c 根，剩下的根数要正好填满后面的 left 位，
//   也就是要落在 [2 * left, 7 * left] 这个区间里。第一个满足的数字就是这一位的最优解
//   （第一位不能选 0）。
// 复杂度 O(len * 10)，len 最多一万多，完全够用。

#include <bits/stdc++.h>
using namespace std;

int match[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main() {
    freopen("sticks.in", "r", stdin);
    freopen("sticks.out", "w", stdout);

    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;

        int len = (int)((n + 6) / 7);              // 最少位数：尽量用 7 根的数字 8
        if (len < 1) len = 1;
        if (2LL * len > n) {                       // 每位至少 2 根，不够就无解
            cout << -1 << "\n";
            continue;
        }

        long long rest = n;
        string ans;
        for (int i = 0; i < len; i++) {
            int left = len - i - 1;                // 这一位后面还剩几位
            for (int d = (i == 0 ? 1 : 0); d <= 9; d++) {
                long long c = match[d];
                long long remain = rest - c;
                if (remain < 0) continue;
                if (remain >= 2LL * left && remain <= 7LL * left) {
                    ans += char('0' + d);
                    rest = remain;
                    break;
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

2024 小木棍 · 方案一 先定位数再贪心

正文

CSP-J 标程 · 复赛真题的其它内容

2024 小木棍 · 方案一先定位数再贪心