从第一个数开始遍历,到找到单调递减的第一个数(即单调递增的最后一个数),则删除,若无单调递减子序列,则删掉最后一个非递减序列的数;每找到一个就又从头开始。即每做一次删数,就是一次贪心选择,删掉此数剩下的数为组成最小,经过证明,此结论正确。
eg:
42135
单调递减的第一个数为第一个数为4,删掉得到2135
之后单调递减的第一个数为2,删掉得到135
不存在单调递减序列,则删除最后一个数5
需要注意的是:2001删除一个数后应该为1,而不是001,需要进行处理
#include
#include
using namespace std;
int shanshu(string &a, int k);
int main() {
string st;
int n, startIndex = 0;
cin >>st >>n;
n = shanshu(st, n);
for (int i = 0; i< n; i++) {
if (st[i] == '0') {
startIndex++;
}
}
for (int i = startIndex; i< n; i++) {
cout<< st[i];
}
return 0;
}
int shanshu(string &a, int k) {
int n = a.size(), j = 0;
while (k >0) {
for (int i = 0; i< n; i++) {
if (a[i] >a[i + 1]) {
for (int j = i; j< n; j++) {
a[j] = a[j + 1];
}
n--;
break; // 忘记退出循环了
} else if (i == n - 1) {
n--;
break;
}
}
k--;
}
return n;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:贪心算法(删数问题)-创新互联
转载来源:https://www.cdcxhl.com/article38/ceeesp.html
成都网站建设公司_创新互联,为您提供搜索引擎优化、网站排名、品牌网站建设、网站导航、网站改版、响应式网站
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联