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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!