删数问题（贪心）

题目描述

给定一个用十进制数字串表示的高精度正整数 n。从中恰好删除 k 位数字后，将剩余数字按它们在原串中的相对顺序拼接成一个新的非负整数。

请输出所有合法删除方案中能够得到的最小整数。

剩余数字串可以含有前导零，但输出时不得保留前导零。如果剩余数字全部为 0，则输出单个0。

输入格式

输入共两行。

第一行是高精度正整数 n。

第二行是正整数 k，表示必须删除的数字位数。

输出格式

输出一个整数，表示删除恰好 k 位后能够得到的最小值。

样例说明

删除数字 7,5,4,8 后，剩余数字按原相对顺序组成13，这是能够得到的最小整数。

数据范围

设 ∣n∣ 表示数字串 n 的长度。保证：

• 1≤k<∣n∣≤250；
• n 只含字符0到9，且首位不为0。

因此，k 不会等于 0，也不会等于 ∣n∣；删除后至少保留一位数字。

数据特征

表中每一行表示：对于前 x% 的测试数据，该行列出的条件同时成立。

#include<bits/stdc++.h> using namespace std; string s; int k; int main(){ cin>>s>>k; if(s.size()==k){ cout<<0; return 0; } int yu=s.size(); while(k--){ for(int i=0; i<yu-1; i++){ //if(i==0 && s[i+1]==0)continue; if(s[i]>s[i+1]){ for(int j=i; j<yu-1; j++) s[j]=s[j+1]; break; } } yu--; } int f=0,m=yu; while(s[f]=='0' && m>1){ f++; m--; } for(int i=f; i<yu; i++) cout<<s[i]; return 0;}