【贪心】删数问题
【问题描述】
给定n位整数q，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
比如，178543删除四个数字后，最小的新数是13。
贪心策略：最近下降点优先。
#include <iostream>#include <vector>#include <string>using namespace std;void delek(vector<int> &s, int k){int n=s.size();if(k>=n);else{while(k>0){ for(vector<int>::iterator it=s.begin(); it<s.end()-1 && *(it)<*(it+1); it++) ; s.erase(it);k--;}}}void main(){vector<int> s;s.push_back(1);s.push_back(7);s.push_back(8);s.push_back(5);s.push_back(4);s.push_back(3);delek(s, 4);for(vector<int>::iterator it=s.begin(); it!=s.end(); it++)cout<<*it;cout<<endl;}