2 qq 33748682 qq_33748682 于 2016.02.05 15:23 提问

对给定的N位高精度正整数,去掉其中的k个数字后,使剩下的数字构成的整数最大。

Input
输入第1行为一个整数L
后面L行的每一行包括一个长度为N的高精度正整数和需要去掉的数的个数k。(1 <= N <= 1000 , 1 <= k < N)

Output
输出每一行表示每个高精度正整数去掉相应的k个数字后构成的新的最大正整数。

Sample Input
Original Transformed
2
12345 1
54321 2

Sample Output
Original Transformed
2345
543
C语言有没有比较好的解决方法或者算法思路,自己编的程序总是出现一些小问题

7个回答

leilba
leilba   Rxr 2016.02.06 17:56

哪个OJ题目吧?
按照我的理解,这题不能排序,要保持原先的顺序,扩展一下几种样例情况以及我所给出的最大数:
123123 3 输出:323
1000 2 输出:10
322123 1 输出:32223
12345 3 输出:45

这题的要求是去掉k个数之后变得尽量大,那么也就是说,要让高位的数尽量大,也就是说,使得数字从高位开始尽量呈现递减的状态(前一位数要比后一位数大或者相等),而且我们在求值的时候是可以利用递推性的,比如k=2的结果可以在k=1的时候的结果上来取,也就是说k的结果可以在k-1的基础上进行获取。
我们以 123123 3 这种情况作为例子分析:
由于k=3,所以要去掉3个数,那么我们先求去掉2个数和去掉1个数的情况。
去掉1个数,也就是输入为123123 1 的时候:我们看123123的第一位和第二位分别是1和2,显然第一位要比第二位小,不符合递减状态,所以我们删掉第一位,那么就变成了 23123
去掉2个数,也就是输入为123123 2 的时候:在去掉1个数的结果23123的基础上,我们需要再去掉一个数。我们看到第一位第二位分别是2和3,显然不符合递减状态,所以删掉第1位的2,么那变成3123
去掉3个数:在去掉2个数的结果3123的基础上,我们看到第一位第二位分别是3和1,符合递减状态,所以我们需要看第二位和第三位,第二位是1第三位是2,显然不符合递减状态,所以删掉第二位,那么得到的是323。

所以,我们可以这样做:
对于每个输入样例,我们需要做k次循环,每次循环所做的事情是从最高位开始遍历,找出不符合递减状态的第一个数,将其删掉。这样在k次循环之后我们就能获取到最大的数。
整理之后的代码:

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

//从start位置开始到end结束,整体后移一位,将end的位置覆盖掉
void moveOneStep(char * bigNum,int start,int end) {
    for (int i=end; i>start; i--) {
        bigNum[i]=bigNum[i-1];
    }
}

int main()
{
    int L;
    //输入L
    scanf("%d",&L);
    while (L--) {
        //做acm的话数组稍微开大一点点,因为有些题目会很坑,可能会出违背题目要求的内容
        char bigNum[1005];
        int k;

        //输入大数
        scanf("%s",bigNum);

        //长度
        long long length = strlen(bigNum);
        //获取k
        scanf("%d",&k);

        if (k >= length) {
            printf("不合法的输入\n");
            continue;
        }

        //核心代码
        for (int i=0; i<k; i++) {
            for (int j=i; j<length; j++) {
                if (bigNum[j] < bigNum[j+1] || j == length - 1 ) {
                    //使用了位移覆盖的方式来删除
                    moveOneStep(bigNum,i,j);
                    break;
                }
            }
        }
        //将字符串前移k位,也就是将原先后移的都移回来
        for (int i=0; i<length - k; i++) {
            bigNum[i] = bigNum[i+k];
        }
        //限定字符串长度为 length - k
        bigNum[length - k ] = '\0';

        printf("%s\n",bigNum);

    }

    return 0;
}

这是用数组来实现的方式,每删除一个都需要位移一次,复杂度近乎为0(n2),其实可以用一个当前位置指针来进行优化,不过复杂度不会有太大变化。
另外也可以用链表来实现,如果用链表来实现的话,删除将会方便很多,实现的思想是差不多的,不过如果借助一个当前位置指针的话复杂度可以下降到0(n)。

caozhy
caozhy   Ds   Rxr 2016.02.05 21:44
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void * a, const void * b)
{
    return *(char *)b - *(char *)a;
}
int main()
{
    char s[100];
    char r[100];
    int n;
    scanf("%s", s);
    strcpy(r, s);
    scanf("%d", &n);
    qsort(s, strlen(s), sizeof(char), cmp);
    int minpos = strlen(s) - 1;
    for (int i = strlen(s) - 1; i >= 0; i--)
    {
        if (r[i] == s[minpos]) { r[i] = '\0'; i = strlen(s); minpos--; }
        if (minpos < strlen(s) - n) break;
    }
    int x = 0;
    for (int j = 0; j < strlen(s); j++)
    {
        if (r[j] != '\0')
        {
            x *= 10;
            x += r[j] - '0';
        }
    }
    printf("%d", x);
    return 0;
}
caozhy
caozhy   Ds   Rxr 2016.02.05 21:46

这个题目有点变态的。正文说的和例子不是一回事。
正确的描述题目的方式是,输出每一行表示每个高精度正整数去掉相应的k个数字后(不改变原先字符顺序)构成的新的最大正整数。

caozhy
caozhy   Ds   Rxr 2016.02.05 21:21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void * a, const void * b)
{
    return *(char *)b - *(char *)a;
}
int main()
{
    char s[100];
    int n;
    scanf("%s", s);
    scanf("%d", &n);
    qsort(s, strlen(s), sizeof(char), cmp);
    s[strlen(s) - n] = '\0';
    printf("%s", s);
    return 0;
} 
xianfajushi
xianfajushi   2016.02.05 17:13

思路就是把最大的数放在最高位,也就是按降序排序

a774057695
a774057695   2016.02.05 17:25

其实核心就是排序(每个数位的数字从大到小)后输出(N-k个),输出没有什么好说的,排序算法也没有什么好说的。将一个数字的每一位取出,有两种思路:
1.循环或者递归 取余
2.数字转字符串按位截取,每一位再转数字
效率上我没有比对过,不过你的数字长度能达到1000,还是直接字符串来表示这个数吧。输出同样也用字符串。

91program
91program   Ds   Rxr 2016.02.05 20:50

先取模取出各位上的数字,对这些数字进行从小到大姐的排序
最后,将排序后的数字乘 10 相加,再组成最终的数字

91program
91program 回复caozhy: 要你多嘴,LZ 自己会判断。你以为你又是老大了,想把自己的思想强加于别人!你他妈的以为你是谁啊!以后你跟一次爷爷的帖子,爷爷就骂孙子一次。你准备好了吗,孙子?
2 年多之前 回复
caozhy
caozhy 这种答案基本上也就是把lz的题目又抄了一遍,而且还抄错了。
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对所给的n和s,寻找一种方案使得剩下的数字组成的新数最小。
#include <iostream> #include <string> using namespace std;//从字符串v中从下标j开始删除s个字符,删除的字符保存在s_del中 void min_num(string &v, int &s,int j,string &s_del) { if ( 0 != s) { //如果j小于0则从第0个字符开始
删数问题(贪心)
删数问题 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 给定n 位(n≤100)正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n 位正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。 对于给定的正整数a,计算删去k 个数字后得到的最小数。
陈利人 面试题 对于一个n位正整数a,去掉其中任意k(k<=n)个数字后,剩下的数字按原次序排列可以组成一个新的正整数。设计一个删数算法,使得剩下的数字组成的正整数最小。
题目 对于一个n位正整数a,去掉其中任意k(k 分析 一个n位数,删去k位后,也就是剩下一个 n-k位 数,那么这个数要最小,我们就要保证我们我们得出的数是所有删除后得到的数的最小值。那么怎么保证呢? 问题转换一下,如果最后就剩下一位,那么无意结果就是这些数字的最小值; 如果最后剩下两位呢,那么我们所要结果的最高位肯定在给定数的哪个区间呢,在这个区间(从左往右数第一位,从右往左数第二位
贪心法删数问题
【题目】 过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按 原左右次序将组成一个新的正整数。编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小。 输入:n s 输出:最后剩下的最小数 【样例输入】 178543 S=4 【样例输出】 13 【分析】 由于正整数n
删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个
删数问题 Description 给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个 新的正整数。对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1 行是1 个正整数a。第2 行是正整数k。 Output 程序运行结束时,将计算出的最小数输出到文件output.txt中。 Sample Input 178543 4 Sample Output 13
键盘输入一个高精度的正整数n(<=240位),去掉任意s(s<n)个数字后,将剩下的数字按原左右次序组成一个新的正整数。
一、题目分析 很经典的一个题目。采用贪心策略。 这个题目其实可以分成两个小题。 1),使剩下的数最小。 2),使剩下的正整数最小。这时,删除的数字数s 就不能等于 n。以及删除后等于0或0...0就不行了。 1, 使剩下的数最小。 思路:依次遍历正整数的各位数字,将单调递减区间的第一个数字删掉,如果整个字符串已经单调递增排列的话,将最后一个删除. 代码(OJ上没有找到这道题,
算法题—n位正整数去掉k(k<=n)位数字得到最小数
问题描述:给定n位正整数a,去掉其中任意k 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 输入:多组测试数据,每组测试数据的第一行是1个正整数a(a,第二行是正整数k(k 输出:删掉个数字后的最小数,每组测试数据输出单独一行,如果首位数字为0,删除首位数字。 #include #define MAX 10000000 int num[MAX]; //返回删除的位置 int
一个正整数去掉s位后得到最小整数
题目具体描述:   键盘输入一个高精度的正整数N(N不超过200位),  去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数:编程对给定的N和S,  寻找一种方案使得剩下的数字组成的新数字最小. 输入: 一个高精度的整数,求掉的元素个数s 输出:一个最小的整数(假设:0开头的整数小于任意的长度相同的非0开头的整数) 算法思想: 构建一个栈,遍历整数的每位元素,使其栈顶元素比
hdu 3183 A Magic Lamp(给一个n位的数,从中删去m个数字,使得剩下的数字组成的数最小(顺序不能变),然后输出)
1.题目大意是,给你一个1000位的数,要你删掉m个为,求结果最小数。 思路:在n个位里面删除m个位,也就是找出n-m个位组成最小数 所以在区间 [0, m]里面找最小的数,对应的下标标号i 接着找区间 [i+1,m++]里面的最小数,对于下标为ii 接着找区间 [ii+1,m++]里面的最小数…… 这样就会找n-m个数了。区间这样安排的目的是为了保证取出来的数的顺序
贪心算法-删数问题
通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的新数最小 算法试卷上看见一道贪心算法的题目,删数问题!!! 题目如下: 【删数问题】通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小。要求在横线上填