NYOJ-448 寻找最大数(贪心)
2024-08-24 09:37:05
NYOJ-448
寻找最大数
时间限制:1000 ms | 内存限制:65535 KB
难度:2
- 描述
-
请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大,
比如当n=92081346718538,m=10时,则新的最大数是9888
输入
- 第一行输入一个正整数T,表示有T组测试数据
每组测试数据占一行,每行有两个数n,m(n可能是一个很大的整数,但其位数不超过100位,并且保证数据首位非0,m小于整数n的位数) - 输出
- 每组测试数据的输出占一行,输出剩余的数字按原次序组成的最大新数
- 样例输入
-
2
92081346718538 10
1008908 5 - 样例输出
-
9888
98 思想:贪心算法,最优子结构达到最优全局解
第一次从头遍历cut个数,找到最大数,并将子结构起始搜索点定在它的下一位,同时将搜索结束点后移一位。 代码:#include <stdio.h>
#include <string.h> int main(void)
{
int T;
scanf("%d", &T);
while (T--)
{
char string[];
int cut;
scanf("%s", string);
scanf("%d", &cut);
int len = strlen(string);
int find_time = len - cut;
char cur_max;
int index = ;
while (find_time--)
{
cur_max = string[index];
for (int i = index; i <= cut; i++)
{
if (string[i] > cur_max)
{
cur_max = string[i];
index = i;
}
}
printf("%c", cur_max);
cut++, index++;
}
putchar('\n');
}
return ;
}
- 第一行输入一个正整数T,表示有T组测试数据
最新文章
- 【工业串口和网络软件通讯平台(SuperIO)教程】二.架构和组成部分
- php字符串处理函数大全
- [LintCode] Valid Palindrome 验证回文字符串
- (转)winform Form 淡入淡出效果
- Hibernate对象映射类型
- Android异步下载网络图片
- HDU 5889 (最短路+网络流)
- .NET面试资料整理
- 定制炫彩界面:duilib与MFC 的对比
- mobile_1 物理像素
- C++ MySQL编程
- SVM探讨
- windows 10 &; task view &; shortcut
- 一、hadoop部署
- CentOS 特殊变量($0、$1、$2、 $?、 $# 、$@、 $*)
- Java代码封装redis工具类
- linux申请strace ,lstrace, ptrace, dtrace
- UVaLive 4628 Jack&#39;s socks (贪心)
- vue webpack 打包后css背景图路径问题
- python将字符转换为字典