2021-03-09
删数是删掉最大的k个数字吗?
答案显然不是,所以我们采取的策略是:
每一次删除都使剩下的数字最小,显然是删除从高位向低位搜到的第一个“山峰”————即那个数比前面的和后面的都要大
而删除第一个山峰则是使第一个山峰那一位的数字达到最小,从而使整个数字最小
策略确定好,代码就不难打出了
如下:
#include<bits/stdc++.h>
using namespace std;
int k;
string n;
int main()
{
cin>>n>>k;
int len=n.size();
for(int i=1;i<=k;i++) //删除s个数
{
for(int j=0;j<len-1;j++)
if(n[j]>n[j+1]) //找到第一个山峰
{
for(int l=j;l<len-1;l++)//删除那个数字
n[l]=n[l+1];
break;//删了一个了,跳出循环
}
len--;//长度减1
}
int w=0;
while(w<len&&n[w]=='0') w++; //删除前缀0
if(w==len) cout<<"0"<<endl;//如果都是0,则答案为0
else for(int i=w;i<len;i++) cout<<n[i]-'0';//把字符转换为数字
return 0;
}