2 qq 33748682 qq_33748682 于 2016.02.05 17:46 提问

对给定的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语言有没有比较好的解决方法或者算法思路,自己编的程序总是出现一些小问题

3个回答

caozhy
caozhy   Ds   Rxr 2016.02.05 22:01
 #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;
}
91program
91program   Ds   Rxr 2016.02.05 19:40

取模运行,获取到各位上的数字,然后从大到小排序,再将排序后的数字组合成一个大数字,即为你想要的。

lm_whales
lm_whales   Rxr 2016.02.05 19:15

查找最小K个数 O(N)
最后j个数如果相同,并且有i-j个需要保留
处理一下应该保留那个方向的

lm_whales
lm_whales 哦。这是另一种最大子序列,
接近 2 年之前 回复
lm_whales
lm_whales 可以用计数排序法
接近 2 年之前 回复
lm_whales
lm_whales 优先删除最前面的
接近 2 年之前 回复
lm_whales
lm_whales j-i
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!