一：題目

有一個(gè)長(zhǎng)度為n（n <= 240）的正整數(shù)，從中取出k（k < n）個(gè)數(shù)，使剩余的數(shù)保持原來的次序不變，求這個(gè)正整數(shù)經(jīng)過刪數(shù)之后最小是多少。

輸入格式:
n和k

輸出格式:
一個(gè)數(shù)字，表示這個(gè)正整數(shù)經(jīng)過刪數(shù)之后的最小值。

輸入樣例:

178543 4

結(jié)尾無空行
輸出樣例:

13

二：思路

思路：
1.首先貪心的策略是每次最優(yōu)，那么結(jié)果就是最優(yōu)的
2.那么這道題我們可以每次刪除序列中 升序的結(jié)尾，重復(fù)上述操作k次，這樣的話我們就能可以
這個(gè)結(jié)果的最優(yōu)解了

解釋：因?yàn)樵谝淮當(dāng)?shù)中，我們想要其刪完某個(gè)數(shù)后其剩下的值最小，我們總想刪除大的數(shù)
那么剩下的數(shù)肯定要小呀 比如 12345 刪除5剩下的數(shù)是最小的

3.當(dāng)然我們也可以刪除每次發(fā)生降序的時(shí)候 就把前一個(gè)數(shù)刪除

三：上碼

/**思路：1.首先貪心的策略是每次最優(yōu)，那么結(jié)果就是最優(yōu)的2.那么這道題我們可以每次刪除序列中 升序的結(jié)尾，重復(fù)上述操作k次，這樣的話我們就能可以這個(gè)結(jié)果的最優(yōu)解了解釋：因?yàn)樵谝淮當(dāng)?shù)中，我們想要其刪完某個(gè)數(shù)后其剩下的值最小，我們總想刪除大的數(shù)那么剩下的數(shù)肯定要小呀 比如 12345 刪除5剩下的數(shù)是最小的 3.當(dāng)然我們也可以刪除每次發(fā)生降序的時(shí)候 就把前一個(gè)數(shù)刪除 **///100012 2 1#include<bits/stdc++.h> using namespace std;int main(){string str;int k,flag = 0;vector<char>v;cin >> str >> k;for(int i = 0; i < str.size(); i++){v.push_back(str[i]);} while(k--){int i = 0;flag = 0;vector<char>:: iterator t = v.begin();//這里主要是為了調(diào)用 v.erase()的庫函數(shù)刪除元素while(i != v.size()-1){//注意這里的減一 因?yàn)橄路降膙[i+1] 否則會(huì)出現(xiàn)段錯(cuò)誤if(v[i] > v[i+1]){//如果出現(xiàn)后一個(gè)數(shù)小于前一個(gè)數(shù)那么這就是這一趟的遞增的終點(diǎn) v.erase(t);flag = 1;break;}i++;t++;}if(flag == 0){//如果是一個(gè)遞增序列那么的話就要?jiǎng)h除最后一個(gè)數(shù) v.erase(t);} } int i = 0;//這么輸出是為了防止前置'0'的輸出for(int i = 0; i < v.size(); i++) {if(v[i] != '0')break; }int j = i; for( ; j < v.size(); j++){cout << v[j];} }

四：記錄失敗碼

這是第一次做時(shí)寫的碼，測(cè)了好多數(shù)據(jù)，終于測(cè)出錯(cuò)誤了，然后就退出算法有問題了但還是想記錄一下 下方的測(cè)試用例可以拿走不謝

/**思路：將輸入的數(shù)據(jù)當(dāng)成字符串處理并進(jìn)行排序，輸出字符串長(zhǎng)度-k個(gè)字符 */#include<bits/stdc++.h> using namespace std;int main(){int n, k;vector<char>v,v1,v2,v3;int count = 0;cin >> n >> k;;stringstream st;st << n;string str = st.str();for(int i = 0; i < str.size(); i++){v.push_back(str[i]);v2.push_back(str[i]);}sort(v.begin(),v.end());for(int i = 0; i < v.size() - k; i++){v1.push_back(v[i]);}for(int i = 0; i < v2.size(); i++){for(int j = 0; j < v1.size(); j++){if(v2[i] == v1[j] && count < v2.size() - k){v3.push_back(v2[i]);//cout << v2[i]; v1[j] = 'a';//當(dāng)統(tǒng)計(jì)過一次v1容器當(dāng)中的元素下次就不在輸出了99913 2 count++;break;}}}for(int i = 0; i < v3.size(); i++){int temp = v3[i] - '0'; if(temp != 0)cout << temp;}} //測(cè)試用例 //1378541 4//378541 4//1378541 6//11378541 6//11378541 5//378541 4//99913 2//100012 1//這個(gè)測(cè)試用例推翻算法 正確結(jié)果應(yīng)是 12 上方代碼輸出10001 // 錯(cuò)誤原因:他存的時(shí)候?qū)?0001存進(jìn)去了v1,那么就永遠(yuǎn)得不到12

總結(jié)

以上是生活随笔為你收集整理的7-9 删数问题 (10 分)（思路加详解）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。