描述:
一个集合有如下元素:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数,现要求从中删除M个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。
注:不存在所有数被删除的情况
难度:普及+/提高
题目类型:贪心/模拟
提交次数:3
涉及知识:贪心/BFS/字符串/优先队列
#include<iostream> #include<queue> #include<cstring> #include<cstdio> using namespace std; int a[30010]; char c[10000]; string s; priority_queue<int, vector<int>, greater<int> > q; int main(){ int k, m, i = 0; cin>>k>>m; q.push(1); while(!q.empty()){ int t = q.top(); q.push(t*2+1); q.push(t*4+5); q.pop(); a[i++] = t; if(i==k) break; } for(i = 0; i < k; i++){ memset(c, 0, sizeof(c)); sprintf(c, "%d", a[i]); s += c; } cout<<s<<endl; //—————————————————————————————————————— int n = 0; i = 0; while(n<m&&i<s.length()-1){ i++; if(s[i-1]<s[i]){ s.erase(i-1,1); n++; i=0; } } for(i = 0; i < m-n; i++) s.erase(s.length()-1, 1); for(i = 0; i < s.length(); i++){ if(s[i]!='0') { cout<<s.substr(i, s.length()-i); return 0; } } if(i==s.length())cout<<'0'; return 0; }