第四章贪心算法实验报告
问题描述:
(删数问题)给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。
输入格式:
第 1 行是1 个正整数 a,第 2 行是正整数k。
输出最小数。
178543
4
13
#include<bits/stdc++.h> using namespace std; char n[100]; int main(){ int k; int len; int flag=1; cin>>n; cin>>k; len=strlen(n); while(k!=0){ for(int i=0;i<len;i++){ if(i==len-1){ len--; break; } else if(n[i]>n[i+1]){ for(int j=i;j<len-1;j++){ n[j]=n[j+1]; } len--; break; } } k--; } for(int i=0;i<len;i++){ if(n[i]=='0'&&i<len-1&&flag==1){ continue; } else{ cout<<n[i]; flag=0; } } }
时间复杂度:主函数中有两层循环体,循环k次,时间复杂度为O(n^2)
空间复杂度:借用一个char数组来存储a,a共有n位,空间复杂度为O(n)