贪心删数问题

碰到的一道可以用到刚学的几个小函数解题，记录一下

#include<bits/stdc++.h>
using namespace std;
int main()
{
   string n;//n为字符串 
   int s,i,x,l;//s为要删除的数字数量，i循环使用，x为s的替代，计数使用，l为字符串长度 
   while(cin>>n>>s)
   {
        i=-1,x=0;
        l=n.length();//string求字符串长度 
        while(x<s)//x表示删除了的数的数量 
        {
             i++;//自增后第一次i为0 
             if(n[i]<n[i+1])//出现递增,删除递减增的首数字 
              {
                  n=n.erase(i,1);//删除下标为i的数 
                  x++;// x统计删除数字的个数 
                  i=-1;//从头开始查递减区间 
              } 
             if(i==l-x-2&&x<s)//无递增区间脱离循环 
             break;//退出循环 
        } 
     cout<<n.substr(0,l-s+x)<<endl;//只打印剩下的左边l-(s-x)个数字 
   } 
   return 0;   
}

第一个函数

n=n.erase(i,1)// 此处意为删除下标‘i’开始的连续1个字符

具体可在此链接查看：https://blog.csdn.net/leo_csdn_/article/details/82221721

第二个函数

cout<<n.substr(0,l-s+x)//此处意为打印下标0到 l-s+x中的字符 ，两个参数，第一个为初始位置，第二个为复制个数，（复制多少个字符到子串中，最后返回的是子字串）

substr是C++语言常用函数（我觉得常用，嘿嘿），主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。如果没有指定长度_Count或_Count+_Off超出了源字符串的长度，则子字符串将延续到源字符串的结尾。

题目来源 www.educoder.net

内容如下

任务描述

本关任务：掌握贪心算法的算法思想，并能利用贪心算法的算法思想解决删除数字问题。

给定nn个纯数字组成的数字串，删除其中k(k < n)k(k<n)个数字后，剩下的数字按原来的秩序组成一个新的正整数，确定删除方案，使得剩下的数字组成的新的正整数最大。

贪心算法的基本概念

贪心算法又称之为贪婪算法，指的是在求解问题时，总是选择当前最好结果的方案，而不从整体考虑最优解法。贪心算法的两个基本要素分别是贪心选择和最优子结构。

贪心选择：求解问题的整体最优解可以通过一系列的局部最优的选择来实现，即贪心选择。
最优子结构：一个问题的最优解包含其子问题的最优解，称此问题具备最优子结构性质。

贪心算法的基本概念如下：

贪心算法是一种着眼局部的简单而适应范围有限的优化策略。
贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，每一阶段所做出的选择只是着眼于局部最优的选择。这样处理，对有些问题来说也能得到最优解，但也并不总是这样。
贪心选择性质：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是一问题可用贪心算法求解的前提，也是贪心算法与动态规划算法的主要区别。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终能达到问题的整体最优。

贪心算法的基本思路步骤

根据贪心算法的基本概念，可以得到贪心算法的基本模型和执行步骤如下：

建立数学模型来描述问题；
把待求解的问题分成若干个子问题；
对每个子问题进行求解，得到子问题的局部最优解；
把子问题的局部最优解组合成原来问题的整体最优解。

删除数字问题求解思路

对于删除数字问题，第一次删除一个数字所得到的最大整数是当前的最优解，然后剩下的整数继续删除一个数字，得到的最大整数仍然是当前的最优解，以此类推，每次删除数字都选择得到当前最优解的策略。因此，最终删除kk个数字后余下的最大整数即为整体的最优解。根据贪心算法的基本步骤，求解思路如下：

设大整数数组为a[0,1,..,n-1]a[0,1,..,n−1]，每个数组元素表示大整数的一位，大整数的最高位为a[0]a[0]，最低位为a[n-1]a[n−1]，用赋值为-1−1来表示删除操作，例如a[1]=-1a[1]=−1，则表示删除数组索引11处的数字；
求解nn个纯数字组成的数字串删除kk个数字后余下最大整数的问题，可以划分为kk个子问题：删除11位数字后余下最大整数问题。
依次对每个子问题求解：从左往右查询（i=0\rightarrow n-2i=0→n−2），对于数组aa中出现的第一个数据对a[i] < a[i+1]a[i]<a[i+1]，删除a[i]a[i]后余下的整数一定比删除a[i+1]a[i+1]后余下的整数要大（其余数字位置不变，相连两个数字中，删除小的数字a[i]a[i]后余下的整数a[0,1,..i-1,i+1,i+2,..n-1]a[0,1,..i−1,i+1,i+2,..n−1]一定比删除大的数字a[i+1]a[i+1]余下的整数a[0,1,..,i-1,i,i+2,..n-1]a[0,1,..,i−1,i,i+2,..n−1]要大，因为新的整数在第ii个位置上的数字前者大于后者）。为了实现方便，而不需要数组移位来形成新的整数，按先前的设定，将a[i]a[i]赋值为-1−1，往后的子问题在求解时注意跳过值为-1−1的数字。
kk个子问题依次求解出最优解之后，得到的整数即为nn个数字串删除kk个数字后余下的最大整数。

上面第33步在求解kk个子问题时用的是暴力尝试的方法，复杂度为O(k*n)O(k∗n)，为了提高算法执行效率，可以维护每个子问题求解后ii的位置，而不是每次都从头开始，这样子的算法复杂度为O(n+k)O(n+k)，具体维护方法是：当a[i]=-1a[i]=−1时，让ii往左移（i=i-1i=i−1），直到i=0i=0或a[i]!=-1a[i]!=−1为止。

编程要求

本关的编程任务是补全右侧代码片段main中Begin至End中间的代码，具体要求如下：

在main中，读取大整数字符串并存入字符数组s，然后将字符数组s转换到整型数组a中。读取整数k（表示要删除k个数字），然后根据贪心策略，求解出删除k个数字后剩下的最大整数，并在一行输出。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

79502867154829179316

8

预期输出：

987829179316

正规一点的，我那个是自己乱写，不按要求

//
//  main.cpp
//  step1
//
//  Created by ljpc on 2018/12/8.
//  Copyright © 2018年 ljpc. All rights reserved.
//

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

using namespace std;

int main(int argc, const char * argv[]) {
    
    char s[1001];
    int a[1001];
    int k;
    int n;
    
    // 请在这里补充代码，完成本关任务
    /********* Begin *********/
	int maxn,t=0,e,l;
	k=1;
    cin>>s+1>>n;
    l=strlen(s+1)-n;
    while(n>0)
    {
        maxn=0;
        for(int i=k;i<=k+n;i++)
        {
            if(s[i]-'0'>maxn&&i<strlen(s)) 
            {
                maxn=s[i]-'0';
                e=i;
            }
        }
        a[t++]=maxn;
        if(t==l) break;
        n-=e-k; k=e+1;
    }
    for(int i=0;i<t;i++) cout<<a[i];
    if(t!=l)for(int i=k;i<strlen(s);i++) cout<<s[i];

    /********* End *********/
    
    return 0;
}