4-2 删数问题 (110 分)
分析程序存储问题。内容包括：
实践题目
问题描述
算法描述（说明你的贪心策略，并且参考会场安排问题，利用反证法证明贪心选择和最优子结构性质）
算法时间及空间复杂度分析（要有分析过程）
心得体会（对本次实践收获及疑惑进行总结）
给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最 小的删数方案。
第 1 行是1 个正整数 a。第 2 行是正整数k。
输出最小数。
在这里给出一组输入。例如：
178543
4
在这里给出相应的输出。例如：
13
贪心策略：高位数越大，这个数就越大，所以我们要从高位来看，高位和下一位比较，从高位到低位看，如果高位大于低位，那么删掉高位的数，如果是递增的数，那么就删最后一位
178543：1<7、递增通过；7<8、递增通过；8>5、递减删除8；
17543：1<7、递增通过；7>5、递减删除7；
1543：1<5、递增通过；5>4、递减删除5；
143：1<4、递增通过；4>3、递减删除4；
得：13
#include<iostream> using namespace std; int main() { int k,n,i,j; bool b[100000]; string a; while(cin>>a>>k) { n=a.length(); for(i=0;i<n;i++) b[i]=true; while(k>0) { for(i=0;i<n;i++) if(b[i]) { for(j=i+1;j<n;j++) if(b[j])break; if(j<n&&a[i]>a[j])break; i=j-1; } if(i==n)break; for(i=0;i<n&&k>0;i++) if(b[i]) { for(j=i+1;j<n;j++) if(b[j])break; if(j<n&&a[i]>a[j]) { b[i]=false; k--; break; } i=j-1; } } for(i=n-1;i>=0&&k>0;i--) if(b[i]) { b[i]=false; k--; } for(i=0;i<n;i++) if(a[i]!=‘0‘&&b[i])break; for(;i<n;i++) if(b[i])cout<<a[i]; cout<<‘\n‘; } return 0; }
时间复杂度：
while(k>0)循环中k变换操作为k--
其内部的for循环为O(n)
即算法时间复杂度为O(n^2)
体会：
更加了解了贪心算法的思想
原文：https://www.cnblogs.com/MTstory/p/11894819.html