删数问题（贪心）及vector相关应用

任务描述

有一个长度为n（n <= 240）的正整数，从中取出s（s < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。

输入格式

第一行输入n和s

输出格式

输出一个整数

输入样例

178543 4

输出样例

13

得到局部最优解的过程：

要点：

1.存储：动态数组或字符串数组

2.如何删数：c++函数或c直接实现

3.删数依据：出现降序

4.特殊序列：单调递增：每次只删尾元素；【单调递减：每次只删首元素（包含在正常删数过程中）】

5.输出：首元素不为0

代码实现：

c++版：

//#include
#include
using namespace std;

int main()
{
	string n;
	cin>>n;
	int s,flag=0;
	cin>>s;
	
	vectorA;
	
	//如果是vectorA，此处应为 A.push_back(n[i]-'0');
	for(int i=0;i:: iterator t=A.begin();
        //为了通过迭代器调用vector的库函数erase（）删除指定元素
		
		for(int i=0;iA[i+1])
			{
				A.erase(t);
				flag=1;
				break;
			}	
			t++;    //t随i变化 
		}
		
		if(flag==0)  //如果是一个递增序列，则需要删去最后一个数 
		A.erase(t);
	}
	
	//防止出现前导0 
	int i=0;
	
	for(i=0;i

c版：

区别仅在于存储和删数方法

#include
#include

char n[200];

int main()
{
	int s,flag=0;
	scanf("%s %d",n,&s);
	
	int len=strlen(n);
	while(s--)
	{
		int i=0;
		flag=0;
		
		for( i=0;in[i+1])
			{
				for(int l=i;l 
 
vector相关应用：删除指定元素 
//通过迭代器调用vector的库函数erase（删除当前第i个元素）；insert（在第i个位置插入一个元素） 
		

        //方法1：

        vector:: iterator t;

		for(t=A.begin();t!=A.end();t++)
		{
			A.erase(t);
			   
		}


        //方法2：

        vector:: iterator t=A.begin();

		for(int i=0;i
 
(1)头文件#include
 
(2)创建vector对象，vector A;    //int 类型
 
(3)尾部插入数字：A.push_back(a);  //a=1
 
(4)使用下标访问元素，A[i]
 
(5)使用迭代器访问元素.
 
vector::iterator t;
 
for(t=A.begin();t!=A.end();t++）
 
(6)插入元素：    vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;
 
(7)删除元素：    vec.erase(vec.begin()+2);删除第3个元素
 
vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始
 
(8)向量大小:vec.size();
 
(9)清空:vec.clear();