首页 > 其他分享 >洛谷题单指南-贪心-P1106 删数问题

洛谷题单指南-贪心-P1106 删数问题

时间:2024-02-23 10:24:12浏览次数:31  
标签:P1106 遍历 int 洛谷题 删掉 删数 贪心

原题链接:https://www.luogu.com.cn/problem/P1106

题意解读:如何删数,让剩下的数最小,贪心选择问题。

解题思路:

先看样例:

175438 
4

第1次遍历:删掉7,剩下15438

第2次遍历:删掉5,剩下1438

第3次遍历:删掉4,剩下138

第4次遍历:删掉8,剩下13,即为结果

所以,贪心策略如下:

1、遍历每一个数,如果前一个数比后一个数大,则删掉前一个数

2、以上过程重复k次,即删除k个数

3、特别的,如果是最后一个数,要和0比较,如果比0大则删掉最后一个数

需要注意两点:

1、如果数全部被删除,答案是0,需要特殊处理

2、删除后,可能出现前导0,输出时需要去除前导0

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 255;

string s;
int a[N], cnt, k;

int main()
{
    cin >> s >> k;
    for(int i = 0; i < s.size(); i++) a[i + 1] = s[i] - '0';
    cnt = s.length();

    while(k--) //删k次
    {
        for(int i = 1; i <= cnt; i++) //从头到尾遍历
        {
            if(a[i] > a[i + 1]) //前面数比后面的数大,则删掉前面的数,注意最后一个数要和0比较
            {
                for(int j = i; j <= cnt; j++) //删掉a[i]
                {
                    a[j] = a[j+1];
                }
                cnt--; //数的数量减少1个
                break;
            }
        }
    }

    if(cnt == 0) cout << 0; //都被删了,输出0
    else
    {
        int i = 1;
        while(!a[i] && i < cnt) i++; //去除前导0
        while(i <= cnt) cout << a[i++];
    }
     

    return 0;
}

 

标签:P1106,遍历,int,洛谷题,删掉,删数,贪心
From: https://www.cnblogs.com/jcwy/p/18028900

相关文章

  • 洛谷题单指南-贪心-P3817 小A的糖果
    原题链接:https://www.luogu.com.cn/problem/P3817题意分析:吃最少的糖果,保证相邻糖果数之和不大于x,需要某种贪心策略。解题思路:依次遍历相邻两盒糖果如果糖果数之和大于x,必须要吃点一部分,使得糖果数之和刚好等于x贪心策略是:优先吃后一盒糖果,因为这样可以更利于后续的判断成立......
  • 洛谷题单指南-贪心-P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
    原题链接:https://www.luogu.com.cn/problem/P1090题意解读:两两合并,是典型的哈夫曼编码算法思想,贪心即可。解题思路:要是合并体力消耗最少,就要让尽可能少的果子越晚合并越好,因此,贪心策略为优先选择数量最少的两堆果子合并,一直到剩下一堆果子,把合并过程中的消耗值累加即可,要快速......
  • 洛谷题单指南-贪心-P1803 凌乱的yyy / 线段覆盖
    原题链接:https://www.luogu.com.cn/problem/P1803题意解读:通过某种贪心策略,使得能参加的比赛数越多越好。解题思路:将比赛按照结束时间由小到大哦排序,贪心策略是优先选择结束时间早的比赛,因为这样能保证后面参加更多其他比赛100分代码:#include<bits/stdc++.h>usingnamespa......
  • 洛谷题单指南-贪心-P1223 排队接水
    原题链接:https://www.luogu.com.cn/problem/P1223题意解读:第i个人接水时,后面的n-i个人就要等待,要使平均等待时间最短,即总等待时间最短,贪心法解题。解题思路:设一共n个人,第i人的接水时间为ti总等待时间为:t1*(n-1)+t2*(n-2)+...+tn直观上,贪心策略应该是让接水时间短的人在前,后面......
  • 洛谷题单指南-递推与递归-P1498 南蛮图腾
    原题链接:https://www.luogu.com.cn/problem/P1498题意解读:观察样例,可以发现,当n=1时,得到最基础的图案:/\/__\当n=2时,将基础图案向下复制两个,并排,然后将之前的图案移到居中的位置/\/__\/\/\/__\/__\当n=3时,再将n=2时的图案向下复制两个,并排,然后将之前的图......
  • 洛谷题单指南-递推与递归-P1228 地毯填补问题
    原题链接:https://www.luogu.com.cn/problem/P1228题意解读:用4种毯子铺满2^k*2^k的区域,留出一个公主位置,输出所有毯子拐角的坐标以及哪种毯子,看起来有点无从下手,可以从k=1,k=2,k=3入手去依次考虑,找到规律,用分治法解决。解题思路:1、当k=1时,即2*2的区域,对于任意一个位置是公主,都......
  • 洛谷题单指南-递推与递归-P1010 [NOIP1998 普及组] 幂次方
    原题链接:https://www.luogu.com.cn/problem/P1010题意解读:输出一个正整数的2的幂次方表示,需要用到二进制数学知识,将整数拆解成2的次幂之和,幂次方也要进行拆解,因此容易想到通过递归处理。解题思路:先看样例,给定整数137,要拆解成2的幂次方之和,先考虑i使得刚好137>=2^i时,i取7,因此2......
  • 洛谷题单指南-递推与递归-P1259 黑白棋子的移动
    原题链接:https://www.luogu.com.cn/problem/P1259题意解读:要打印最终的状态,关键在找到一些变化的规律,直接的暴力搜索复杂度太高。解题思路:从样例出发ooooooo*******--oooooo--******o*oooooo******--o*ooooo--*****o*o*ooooo*****--o*o*oooo--****o*o*o*oooo****--o*o*o*ooo--......
  • 洛谷题单指南-递推与递归-P3612 [USACO17JAN] Secret Cow Code S
    原题链接:https://www.luogu.com.cn/problem/P3612题意解读:字符串加长的时候,是先把最后一个字符接上,再拼接其余字符,注意不是翻转,要找第n个字符,就要看字符串加长几次后长度能超过n,然后在加长后的字符串中找第n个字符。解题思路:如果直接通过模拟法,字符串长度太长,且要找的第n个数......
  • 洛谷题单指南-递推与递归-P1990 覆盖墙壁
    原题链接:https://www.luogu.com.cn/problem/P1990题意解读:用两种可旋转的形状铺满N*2的区域,求方案数,可以使用递推。解题思路:步骤1、设f[i]表示铺满i*2的区域的方案数根据要求,i*2区域最后一列有4种可能的铺法:如果采用图1铺法,则有f[i]=f[i-1]如果采用图2铺法,则有f[i]=f......