博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[Swust OJ 403]--集合删数
阅读量:7016 次
发布时间:2019-06-28

本文共 2184 字,大约阅读时间需要 7 分钟。

 

题目链接:

Time limit(ms): 5000        Memory limit(kb): 65535
 
Description
一个集合有如下元素:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数,现要求从中删除M个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。 
注:不存在所有数被删除的情况
 
Input
输入的仅一行,K,M的值,K,M均小于等于30000。
 
Output
输出为两行,第一行为删除前的数字,第二行为删除后的数字。
 
Sample Input
5 4
Sample Output
137915
95
 
解题思路:处理的不好的话就坑爹了,为了int转换string方便偷懒,百度了sstream头文件用法,也算学到了~~~~
     (1)利用题中集合信息得到最小的几个数字
     (2)sstream,int 转换为string的到待删除序列
     (3)贪心---得到删除后的最大数值
 
代码如下(略搓):
1 #include 
2 #include
3 #include
4 #include
5 #include
//int 转 string 6 using namespace std; 7 typedef long long LL; 8 int main(){ 9 int len, m, front, cnt, end;10 LL x[60010] = { 0, 1 }, a, b;11 while (cin >> len >> m){12 int i = 1, j = 1, k;13 for (k = 2; k <= len; k++){14 a = x[i] * 2 + 1;15 b = x[j] * 4 + 5;16 if (a > b){17 j++;18 x[k] = b;19 }20 else if (a == b){21 i++;22 j++;23 x[k] = a;24 }25 else{26 i++;27 x[k] = a;28 }29 }30 string s = "", ans = "";31 for (i = 1; i <= len; i++){32 stringstream ss;33 string str;34 ss << x[i];35 ss >> str;36 s += str;37 }38 cout << s << endl;39 string::iterator it = s.begin();40 s.insert(it, '9');//有效序列从1开始,防止front越界41 len = s.size();42 front = cnt = 0, end = 1;43 while (end <= len && cnt != m){44 if (s[end] <= s[front])45 s[++front] = s[end++];46 else{47 front--;48 cnt++;49 }50 }51 while (end <= len)52 s[++front] = s[end++];53 for (i = 1; i < len - m; i++)54 cout << s[i];55 cout << endl;56 }57 return 0;58 }
View Code

 

转载于:https://www.cnblogs.com/zyxStar/p/4609277.html

你可能感兴趣的文章
HTML-002
查看>>
应对刷新闪烁问题
查看>>
第十一周项目1-存储班长信息的学生类
查看>>
解决手机浏览器顶部下拉出现网页源或刷新的问题
查看>>
正则表达式
查看>>
python开发第一步
查看>>
Mybatis自动生成的配置实例
查看>>
kvm 基本运维命令
查看>>
PID 29364
查看>>
设计模式-状态模式(25)
查看>>
group by查询每组时间最新的一条记录
查看>>
struts2--前台数据通过参数传给后台,后台如何获取参数
查看>>
HDU 4054 Hexadecimal View【模拟】【字符串处理】
查看>>
配置cordova的android开发环境(无android studio)
查看>>
监控glusterfs
查看>>
tomcat 启动慢问题
查看>>
map-reduce流程图
查看>>
【经验】CentOS 5.2 下用Yum安装Apache+PHP+MySQL环境
查看>>
linux centos service 参数详解
查看>>
利用层次遍历原理构建二叉树
查看>>