/洛谷 P1106 删数问题 //此题与 1231 最小新整数 基本雷同 //1231 最小新整数 //感觉题目比较简单,将最大的数由大到小删除 //样例通过,但提交,未通过 //总觉得算法不对,因为删的是最大的数,但又举不出反例 //http://blog.csdn.net/c20190102/article/details/52350828此文介绍得真不赖,摘抄如下: //此题先看看思路: //如果是直接删掉最大的数字,很容易便可举出反例: //1529 1 //如果直接删最大的9,结果为152,如果删掉5,结果为129,显然删掉5才是最佳答案。 //再看一组数据: //141519 2 //如果删最大的9,5,结果为1411,如果删掉4,5,结果为1119,显然删掉4,5才是最佳答案。 //发现什么了吗? //先看第一组: //1 5 1 9 //小大 小 大 //留删 留 留 //第二组: //1 4 1 5 1 9 //小 大 小 大 小 大 //留 删 留删 留 留 //删掉的是“山峰”,也就是比后一个数大的数,且越靠前“山 //峰”越早删。 //大体思路也就一句话:删除靠前的“山峰”。 //另外,有几个坑不得不提: //1.注意删除前导0(虽然它说每个数位都不为0,但是测试数据里面好像有这样的数据)。 //2.删过一个数记得长度len--。 //3.有多组数据(其实数组可以不清零,因为有len控制查找范围)。 //4.当把数删为0(见数据4)时,要输出0。 //另外送大家几组数据(我就在此栽过跟头): // 输入 输出 //133420 2 120 //1444 3 1 //20018 2 1 //10000 1 0 //http://blog.csdn.net/qq_25734657/article/details/52329863代码简练,此文也写得不错,摘抄如下: //1243865 1怎么删呢?如果你认为是删8,那就错了。如果删8,得124365,但如果删4,得123865,哪个更小呢?毫无疑问是后者吧。那如果是1244444 5呢?最后删到124就删不掉了,所以还有一个条件,如果删了一遍,删不掉,就删去最后一个。大概意思就是这样,由于这道题没有出现有0的情况,所以我在这里暂时不讨论,可以自己想想。 //代码彻底推翻重来,样例通过,提交,未通过, //少了break,修改,提交AC 2017-11-2 22:26 //提交,测试点2,6答案错误 //提供两组测试数据 //输入: //20018 2 //输出: //1 //输入: //10000 1 //输出: //0 //针对上述两组输入输出数据进行修改,提交AC 2017-11-26 17:13 #include <stdio.h> #include <string.h> char c[260]; int main(){ int len,i,j,s; scanf("%s%d",c,&s); len=strlen(c); while(s--){ for(i=0;i<=len-2;i++) if(c[i]>c[i+1]){ for(j=i;j<=len-2;j++) c[j]=c[j+1]; break; } len--;//此处位置写错,之前写在if内部 } i=0; while(i<=len-1&&c[i]=='0')i++;//处理前导0 if(i==len)printf("0"); else for(j=i;j<=len-1;j++) printf("%c",c[j]); return 0; }
思路二:选数
思路三:ST算法