貪心算法（刪數(shù)問題）-創(chuàng)新互聯(lián)

數(shù)學(xué)原理：

從第一個(gè)數(shù)開始遍歷，到找到單調(diào)遞減的第一個(gè)數(shù)（即單調(diào)遞增的最后一個(gè)數(shù)），則刪除，若無(wú)單調(diào)遞減子序列，則刪掉最后一個(gè)非遞減序列的數(shù)；每找到一個(gè)就又從頭開始。即每做一次刪數(shù)，就是一次貪心選擇，刪掉此數(shù)剩下的數(shù)為組成最小，經(jīng)過證明，此結(jié)論正確。

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括清流網(wǎng)站建設(shè)、清流網(wǎng)站制作、清流網(wǎng)頁(yè)制作以及清流網(wǎng)絡(luò)營(yíng)銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，清流網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到清流省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

eg：

42135

單調(diào)遞減的第一個(gè)數(shù)為第一個(gè)數(shù)為4，刪掉得到2135

之后單調(diào)遞減的第一個(gè)數(shù)為2，刪掉得到135

不存在單調(diào)遞減序列，則刪除最后一個(gè)數(shù)5

需要注意的是：2001刪除一個(gè)數(shù)后應(yīng)該為1，而不是001，需要進(jìn)行處理

#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; ?// 忘記退出循環(huán)了
 ? ? ? ? ?  } else if (i == n - 1) {
 ? ? ? ? ? ? ? ?n--;
 ? ? ? ? ? ? ? ?break;
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?k--;
 ?  }
 ? ?return n;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：貪心算法（刪數(shù)問題）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://muchs.cn/article38/ceeesp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供搜索引擎優(yōu)化、網(wǎng)站排名、品牌網(wǎng)站建設(shè)、網(wǎng)站導(dǎo)航、網(wǎng)站改版、響應(yīng)式網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容