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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
输入一个高精度的正整数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,寻找一种方案,使得剩下的数字组成的新数最小。要求在横线上填