【题解】删数游戏

川长思鸟来 2021-11-11 03:58 335阅读 0赞

# 题目描述 #

输入一个高精度的正整数n（≤240位），去掉其中任意s个数字后，剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。

## ##

# 输入格式 #

第一行，一个正整数n；

第二行，s（s＜n的位数）。

# 输出格式 #

最后剩下的最小数。

# **输入样例** #

175438

4

# **输出样例** #

13

#### ####

# 题解 #

容易想到，把当前的数转换成一个数字串，那么这个数字串里如果出现了逆序对，就删除这个逆序对的第一个元素即可。如果不存在逆序对，就删除最后一位即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstring>
    #define MAXN 260
    
    using namespace std;
    
    char a[MAXN];
    int sa;
    int s;
    
    int main()
    {
        cin >> a;
        sa = strlen(a);
        a[sa] = 0;
        cin >> s;
        while(s--) for(register int i = 0; i < sa; i++)
        {
            if(a[i] > a[i + 1])//逆序则删除当前的数字 
            {
                for(register int j = i; j < sa; j++)
                    a[j] = a[j + 1];
                sa--;
                break;
            }
        }
        for(register int i = 0, op = 0; i + 1 < sa; i++) 
            if(op || a[i] != '0') op = 1, cout << a[i];//去除前导0 
        cout << a[sa - 1];
        return 0;
    }

参考程序

转载于:https://www.cnblogs.com/kcn999/p/10799438.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/4f73ca8b4e664d328cbe1e8537bc3a96.png

发表评论取消回复

表情：

评论列表（有 0 条评论，335人围观）

还没有评论，来说两句吧...

相关阅读

相关 [BJOI2019]删数

[题目][Link 1] 考虑一个不用修改就能删空的序列长什么样子设\\(cnt\_i\\)表示\\(i\\)出现的次数，我们可以视为在\\(i\\)位置有一根高度为\\

拼搏现实的明天。/ 2023年10月11日 05:29/ 0 赞/ 8 阅读

相关删数问题

删数问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定n 位（n≤100）正整数a，

短命女/ 2022年08月10日 05:57/ 0 赞/ 205 阅读

相关删数问题

Problem Description 键盘输入一个高精度的正整数n（≤100位），去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与

小鱼儿/ 2022年07月12日 02:41/ 0 赞/ 131 阅读

相关删数问题

删数问题 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

朴灿烈づ我的快乐病毒、/ 2022年07月12日 01:28/ 0 赞/ 139 阅读

相关删数问题

删数问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic][S

妖狐艹你老母/ 2022年06月17日 09:49/ 0 赞/ 124 阅读

相关 CSU----E: 删数游戏

ACM小组喜欢上了一个无聊的游戏，游戏的过程是输入一个正整数n，去掉n的任意S个数字后，把剩下的数字看作是一个新的整数（去除前导零）。对给定的N和S，寻找一种删数规则使得剩下的

「爱情、让人受尽委屈。」/ 2022年06月14日 02:37/ 0 赞/ 142 阅读

相关丑数题解

写在前面 > 剑指offer 编程题：丑数。参考目录题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，

分手后的思念是犯贱/ 2022年05月19日 10:39/ 0 赞/ 132 阅读

相关删数问题

删数问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description

向右看齐/ 2022年05月16日 13:09/ 0 赞/ 148 阅读

相关题解[ZJOI2007]矩阵游戏

详谈二分图最大匹配解法和网络流 Dinic解法 1.题目分析 2.匈牙利二分图匹配解法 3.Dinic网络流解法 -----------------

Love The Way You Lie/ 2021年12月22日 05:49/ 0 赞/ 210 阅读

相关【题解】删数游戏

题目描述输入一个高精度的正整数n（≤240位），去掉其中任意s个数字后，剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得

川长思鸟来/ 2021年11月11日 03:58/ 0 赞/ 336 阅读