侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS, 回溯】最大数字【蓝桥杯】

GabrielxD
2023-03-30 / 0 评论 / 0 点赞 / 227 阅读 / 1,308 字
温馨提示:
本文最后更新于 2023-03-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

最大数字 - 蓝桥云课


问题描述

给定一个正整数 NN 。你可以对 NN 的任意一位数字执行任意次以下 2 种操 作:

  1. 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。

  2. 将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。

你现在总共可以执行 1 号操作不超过 AA 次, 2 号操作不超过 BB 次。 请问你最大可以将 NN 变成多少?

输入格式

第一行包含 3 个整数: N,A,BN, A, B

输出格式

一个整数代表答案。

样例输入

123 1 2

样例输出

933

样例说明

对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。

评测用例规模与约定

对于 30%30 \% 的数据, 1N100;0A,B101 \leq N \leq 100 ; 0 \leq A, B \leq 10

对于 100%100 \% 的数据, 1N1017;0A,B1001 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 512M

解题

方法一:DFS 回溯

思路

本题看起来像是从最高位开始的贪心,但其实是个暴搜题。

首先明确:要得到最优解,对于数字中的某一位必须要么做操作 11,要么做操作 22 ,而不能两种操作都做,因为操作 1122 是相悖的,两种都做只会浪费次数

接下来确定对于数中某一位有多少种情况,对于某一位来说:

  1. 剩余的 AA 次数足以使它通过 11 号操作99 ;但剩余的 BB 次数不足以使它通过 22 号操作99 。那就消耗 AA 次数把它加到 99 (把一位数变为 99 是最优先操作)。
  2. AA 次数不够;BB 次数够。那就消耗 BB 次数把它减到 99
  3. AA 次数够;BB 次数也够。那就分两个分支分别尝试 消耗 AA 次数把它加到 99 和 消耗 BB 次数把它减到 99
  4. AA 次数不够;BB 次数也不够。此时只能消耗 AA 次数把该位加大。因为若使用 BB 也减不到 00 ,那么就只会减小该位,这是负贡献的!

接下来的暴搜就好写了:dfs(i,inc,dec)dfs(i, inc, dec)ii 表示当前要操作第几位(从高位开始),incinc 表示还剩多少次加操作,decdec 表示还剩多少次减操作 )

  • 出口:当枚举越界时 ini \ge n ,更新 NN 的最大值。
  • 记录当前位上的数是 d=num[i]d=num[i] ,那么要把它加到 99 需要 up=9dup=9-d 次,减到 99 需要 down=d+1down=d+1 次;
    • incupinc \ge up 对应上面第 (1) / (3) 种情况,消耗 upupincincnum[i]num[i] 加到 99 。搜下一位: dfs(i+1,incup,dec)dfs(i + 1, inc - up, dec) ,搜完后回溯(恢复当前位: num[i]=dnum[i] = d )。
    • decdowndec \ge down 对应上面第 (2) / (3) 种情况,消耗 downdowndecdecnum[i]num[i] 减到 99 。搜下一位: dfs(i+1,inc,decdown)dfs(i + 1, inc, dec-down) ,搜完后回溯(恢复当前位: num[i]=dnum[i] = d )。
    • inc<up&dec<downinc < up \,\&\, dec < down 对应上面第 (4) 种情况,把 incinc 全部用完以把 num[i]num[i] 加到 num[i]+incnum[i] + inc 。搜下一位: dfs(i+1,0,dec)dfs(i + 1, 0, dec) ,搜完后回溯(恢复当前位: num[i]=dnum[i] = d )。

每一位的选择最多也就 22 种,所以这么做的时间复杂度是 O(2log10N)O(2^{\log_{10}{N}}) ,本题中 100%100\% 的数据下最差时间复杂度是 O(217)O(105)O(2^{17}) \approx O(10^5) 完全可以过。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int[] num;
    static long ans = 0L;

    static void dfs(int i, int inc, int dec) {
        if (i == n) {
            long res = 0L;
            for (int x : num) res = res * 10 + x;
            ans = Math.max(res, ans);
            return;
        }
        int d = num[i], up = 9 - d, down = d + 1;
        if (inc >= up) {
            num[i] = 9;
            dfs(i + 1, inc - up, dec);
            num[i] = d;
        }
        if (dec >= down) {
            num[i] = 9;
            dfs(i + 1, inc, dec - down);
            num[i] = d;
        }
        if (inc < up && dec < down) {
            num[i] += inc;
            dfs(i + 1, 0, dec);
            num[i] = d;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        n = s.length;
        num = new int[n];
        for (int i = 0; i < n; ++i) num[i] = s[i] - '0';
        int inc = in.nextInt(), dec = in.nextInt();
        dfs(0, inc, dec);
        System.out.println(ans);
    }
}
0

评论区