洛谷P1106 && TZOJ:6300:删数问题

?标签:贪心

删数问题

题目描述

键盘输入一个高精度的正整数?N（不超过?250位），去掉其中任意?k?个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的?N?和?k，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数?n。

第二行输入一个正整数?k，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

样例 1

样例输入 1

175438 
4

样例输出 1

13

?讲讲思路:

最开始,删数嘛,肯定是想找出最大的数进行删除,然后尽量删除高位的数.

但显然这种方法是有问题的!

?为什么呢,因为没有考虑到数字0!

因为0是不能当作首位的!如果直接删除最大的数

举个例子 100012?要删一个数,删除2?会得到10001?但删除首位的1 ,则会得到12?哪个大不用我多说

所以为什么不换个思路呢

删除 =?保留

如果说要删k个数,换个思路不就是保留len -?k个数吗(len为总长度)

那要怎么保留,显然是尽量让最小数变成高位,那重点是我们要保留len -?k个数

那么我们可以在尾部先暂时保留k-1个数,等取完一个数,后面就再开放一个数

同时要更新起点和终点,讲起来有点抽象,我举个例子

例如

150743这个数,我们要删3个数

1.把他看成两部分 1507?和 43 ,在1507中取最小值0

2.更新起点终点,现在这个数剩下743把他看成两部分 74?和 3?在74取最小值4

3.更新起点终点,现在这个数剩下3?直接取3

4.那么我们就得到了 043 ,删除前导0

5.得到答案43?

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 250; // 范围限制
char s[N]; // 240位 用字符型数组读入
int n ,a[N] , p = 0;

void del() // 删除前导0函数
{
    /* 统计前导零的个数 */
    int i = 0; 
    while(i < p)
    {
        if(a[i] == 0)
            i ++;
        else break;
    }
        
    /* 直接替换 */
    for (int j = 0; j < p - i; j ++ )
        a[j] = a[j + i];
    
    /* 判断是否全为零 */
    if(i == p) p = 1;
    else p -= i;
    
    return ; // 表示一下该函数结束
}

int main()
{
    /* 正常读入 */
    cin >> s >> n; 
    
    /* 初始化 */
    int len = strlen(s);
    int j = len - n;
    int u = -1;
    /* 
        len 存字符串长度
        j 存需要留存的数量
        u 存每次取到的最小值
    */
    
    /* 核心代码 */
    while(p < len - n)
    {
        int mi = u + 1; // 每次初始化mi(只要在范围内即可)
        for (int i = len - j; i > u; i -- ) // 寻找最小值位置
        {
            if(s[mi] - '0' >= s[i] - '0') mi = i;
        }
            
        a[p ++] = s[mi] - '0'; // 添加最小值
        u = mi; //记录最小值位置
        j --; //取一个减一个
    }
    
    /* 删除前导零 */
    del(); 
    
    /* 
        输出进行判断:
        1.删的数量比字符串长 输出0
        2.否则 输出数组a
    */
    if(len > n)
        for (int i = 0; i < p; i ++ ) cout << a[i];
    else cout << "0";
    
    return 0; // 好习惯(^-^)
}

?看起来还是有点繁琐,那么为什么不直接输出?

优化后如下

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 250;
char s[N];
int n ,a[N] , p = 0;

int main()
{
    cin >> s >> n;
    
    int len = strlen(s);
    int j = len - n;
    int u = -1;
    bool f = false; // 判断有无输出
    while(p < len - n)
    {
        int mi = u + 1;
        for (int i = len - j; i > u; i -- )
        {
            if(s[mi] - '0' >= s[i] - '0') mi = i;
        }
            
        a[p ] = s[mi] - '0';
        u = mi;
        j --;
        
        if(a[p]  || !a[p] && a[p- 1]) cout << a[p] , f = true; //前导0不输出 
        p ++;
    }
    if(!f) cout << "0"; 无输出,输出0
}