【C语言】求最小新整数(贪心算法)

简介: 【C语言】求最小新整数(贪心算法)

题目描述

给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。

现在从m位中删除k位(0

例如: n = 9128456, k = 2, 则生成的新整数最小为12456


输入

第一行t, 表示有t组数据;

接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。


输出

t行,每行一个数字,表示从n中删除k位后得到的最小整数。


输入样例

2

9128456 2

1444 3

输出样例

12456

1


方法一

#include
using namespace std;
int k;
main()
{
  int t;
  cin>>t;
  while(t--)
  {
  string n; 
  cin>>n>>k;
  int len=n.size();
  while(k--)
    for(int i=0;i
    if(n[i]>n[i+1]||i==len-1) //删除遇到的第一个递减序列的第一个数字(若整个字符串为非递减序列,则删去末尾的数字)
    {
      n.erase(i,1); //把当前字符从字符串中删除
      break; //不可省略,否则字符串会多删字符
    }
  while(n[0]=='0'&&n[1]) //去掉前缀0,并至少保留1个数字
    n.erase(0,1); //删去当前字符串开头的'0'
  cout<
  }
}


方法二

#include
#include
int main() {
    int t, k;
    char a[200];
    scanf("%d", &t); 
    while (t--) { 
        int i, j, l;
        scanf("%s %d", a, &k); 
        int len = strlen(a); 
        for (i = 0; i < k; i++) { // 执行 k 次删除操作
            for (j = 0; j < len - 1; j++) { // 找到第一个逆序对并删除
                if (a[j] > a[j + 1]) {
                    for (l = j; l < len - 1; l++) { // 删除逆序对
                        a[l] = a[l + 1];
                    }
                    break;
                }
            }
            len -= 1; // 每删除一个字符,字符串长度减一
        }
        for (i = 0; i < strlen(a) - k; i++) { // 输出删除后的字符串
            if (i == 0 && a[i] == '0') { // 如果删除后的字符串以0开头,则跳过0
                continue;
            }
            printf("%d", a[i] - '0');
        }
        printf("\n");
    }
    return 0;
}


目录
相关文章
|
23天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
4月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
113 1
|
22天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
23天前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
41 2
|
23天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
39 1
|
23天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
6月前
|
C语言
【C语言刷题每日一题#牛客网BC6】输入三个整数,输出第二个整数
【C语言刷题每日一题#牛客网BC6】输入三个整数,输出第二个整数
|
2月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
2月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)