P1106 删数问题
Albatross_LC · · 个人记录
本蒟蒻的第一篇题解
题目传送门|博客品尝更佳
这是一道非常经典的贪心题,还要用到高精字符串,要求追后剩下的最小的数,我们可以先来一个暴力,遍历亿遍,将最大的数
code 1.0:
#include<bits/stdc++.h>
using namespace std;
int n[9102],s,zx=2399,j;
string m;
int main(){
cin >> m >> s;
int l=m.size();
for(int i=0;i<l;i++){
n[i]=m[i]-'0';
if(n[i]<zx && n[i]!=0)zx=n[i],j=i;
}
if(j==s){
for(int i=j;i<l;i++)cout << n[i];
return 0;
}
for(int i=1;i<=s;i++){
if(i>j)break;
int max=-1,o;
for(int y=0;y<j;y++)if(n[y]>max)max=n[y],o=y;
n[o]=-1;
}
if(s>j){
for(int i=1;i<=s-j;i++){
int max=-1,o;
for(int y=j+1;y<l;y++)if(n[y]>max)max=n[y],o=y;
n[o]=-1;
}
}
for(int i=0;i<l;i++)if(n[i]!=-1)cout << n[i];
}很显然这是行不通的,当我们交上去时,可以发现只得了28分,(逃).
我们花高价玩儿一个数据:
输入:
50074897 2
正确输出:
4897
实际输出:
004897
这时,我们发现像有0这样的数字,还要去掉开头的0,因此,代码如下:
code 2.0:
#include<bits/stdc++.h>
using namespace std;
int n[9102],s,zx=2399,j;
string m;
int main(){
cin >> m >> s;
int l=m.size();
for(int i=0;i<l;i++){
n[i]=m[i]-'0';
if(n[i]<zx && n[i]!=0)zx=n[i],j=i;
}
if(j==s){
for(int i=j;i<l;i++)cout << n[i];
return 0;
}
for(int i=1;i<=s;i++){
if(i>j)break;
int max=-1,o;
for(int y=0;y<j;y++)if(n[y]>max)max=n[y],o=y;
n[o]=-1;
}
if(s>j){
for(int i=1;i<=s-j;i++){
int max=-1,o;
for(int y=j+1;y<l;y++)if(n[y]>max)max=n[y],o=y;
n[o]=-1;
}
}
int qwq=0;
while(n[qwq]==-1||n[qwq]==0)qwq++;
for(int i=qwq;i<l;i++)if(n[i]!=-1)cout << n[i];
}当我们兴奋递交上去时,发现只多了14分
继续逃
我们再花高价买玩儿一组数据:
输入:
68129545206 6
正确输出:
12206
实际输出:
12420
! ! !
我们忽略了一种数据,这种数据
结论:
从高位往后一直删掉那个比后面的数大的数,结果才最小
比如上面的"219 1",
温馨提示:不要忘记'0'欧!
AC code:
#include<bits/stdc++.h>
using namespace std;
int s,o=0;
char n[392103];
int main(){
cin >> n >> s;
int l=strlen(n);
while(s--){
for(int i=0;i<l;i++){
if(n[i]>n[i+1]){
for(int j=i;j<l-1;j++)n[j]=n[j+1];//如果n[i]>n[i+1],删去这个数
break;
}
}
l--;
}
int p=0;
while(n[p]=='0')p++;//0处理
for(int i=p;i<l;i++)cout << n[i];
if(p>=l)cout << "0";//0处理
}