MIOJ #9 移除 K 位得到最小值

描述

有一行由 N 个数字组成的数字字符串,字符串所表示的数是一正整数。移除字符串中的 K 个数字,使剩下的数字是所有可能中最小的。

假设:

  • 字符串的长度一定大于等于 K
  • 字符串不会以 0 开头

输入

一行由 N 个数字组成的数字字符串(0 < N < 20),和一个正整数 K(K < N),两个数据由空格隔开,如:1432219 3。

输出

移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219,为所有可能中的最小值。

输入样例

1432219 3
10200 1

输出样例

1219
200

AC代码:

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


string removeKdigits(string num, int k)
{
    bool flag = false;//判断是否有前缀0
    string res = "";
    string result = "";
    int temp = 0;
    stack<int>a;
    for(int i = 0; i < num.size(); i++)
    {
        int number = num[i] - '0';
        while( !a.empty() && a.top() > number && k>0)
        {
            a.pop();
            k--;
        }

        a.push(number);
    }
    while(!a.empty() && k>0)
    {
        a.pop();
        k--;
    }
    while(!a.empty())
    {
        temp = a.top();
        stringstream s1;
        string s2;
        s1<<temp;
        s1>>s2;
        res = res+s2 ;
        a.pop();
    }
    for(int i = res.length()-1; i>=0; i--)
    {
        if(res[i]!='0')
        {
            flag = true;
        }
        if(flag)
        {
            result = result + res[i];
        }
    }
    if(result.size() == 0){
        result = "0";
    }
    return result;
}

int main()
{
    string s;
    vector<int>a;
    int k = 0;
    int cnt = 0;
    while(cin>>s>>k)
    {
        cout<< removeKdigits(s,k)<<endl;
    }
}

 

2 comments

  1. 嘿嘿嘿,来晚妹这里蹭粉
    #include
    #include
    using namespace std;
    int main(){
    int K;
    vectora(0);
    char c;
    //————————–处理输入 —————————————–
    while((c=getchar())!=’ ‘) a.push_back(c);
    cin>>K;

    if(K==a.size()) cout<0){
    for(int i=0;i=a[i+1]) {
    a.erase(a.begin()+i);K–;/*cout<<endl<<"erase a[i] K="<<K;*/break;}
    else{
    a.erase(a.begin()+i+1);K–;/*cout<<endl<<"erase a[i+1] K="<1) {a.erase(a.begin()); }

    for(int i=0;i<a.size();i++) cout<<a[i];

    }

    return 0;
    }

  2. 被吞掉了 嘤嘤嘤
    #include
    #include
    using namespace std;
    int main(){
    int K;
    vectora(0);
    char c;
    //————————–处理输入
    while((c=getchar())!=’ ‘) a.push_back(c);
    cin>>K;

    if(K==a.size()) cout<0){
    for(int i=0;i=a[i+1]) {
    a.erase(a.begin()+i);K–;/*cout<<endl<<"erase a[i] K="<<K;*/break;}
    else{
    a.erase(a.begin()+i+1);K–;/*cout<<endl<<"erase a[i+1] K="<1) {a.erase(a.begin()); }

    for(int i=0;i<a.size();i++) cout<<a[i];

    }

    return 0;
    }

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注