Acwing-4653. 数位排序

2023-11-17

本题重点在于预处理每个数的各位之和、cmp函数的书写,根据题目中的描述:当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。不难写出cmp函数。

快速排序的比较次数为nlogn次,本题中约为2*10^7,如果每次都要算这个数的各位之和的话,由于n最大是10^6,也就是6位,再计算6次,总共是2*10^7 * 6 = 1.2 * 10^8 可能会超时。

如何优化呢?我们可以先开个数组s[N],把1-1000000这些数,每个数的各位之和先存下来,这样的话我们在比较的时候就不用现算了,就可以通过查表的方式查出来每个数的各位之和是多少,查表的话只需要一次运算。注:s[i]表示i的各位数之和是多少。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int w[N], s[N];

bool cmp(int a, int b)
{
    if (s[a] < s[b]) return true;
    if ((s[a] == s[b]) && a < b) return true;
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) 
    {
        w[i] = i;
        int j = i;
        while (j) s[i] += j % 10, j /= 10;
    }
    
    sort(w + 1, w + 1 + n, cmp);
    
    printf("%d", w[m]);
    return 0;
}

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Acwing-4653. 数位排序 的相关文章

  • 打击垃圾邮件机器人

    我的网站中有 C 表单 希望防止垃圾邮件机器人填写它 诀窍是 我想避免 CAPTHA 或任何其他用户输入 以避免丢失单个注册 以下是我心中的一些技巧 隐藏输入栏 问题 这还有效吗 跟踪时间 从第一个用户输入 关注名字 到发布表单 人类需要
  • 运行 t4 脚本作为 resx 文件的自定义工具

    我有一个资源文件MyResource resx 我想改变MyResource Designer cs文件生成 我有一个 t4 脚本 它接受 resx 文件作为输入并给出结果转换 但是 我必须手动运行此 t4 才能使其工作 我看到 resx
  • 对静态成员变量的未定义引用

    我有一个有静态成员的类 它也是我的程序中其他几个类的基类 这是它的头文件 ifndef YARL OBJECT HPP define YARL OBJECT HPP namespace yarlObject class YarlObject
  • WP8.1 C# 绑定联系人图像

    信息很简单 我正在尝试创建一个可以显示用户联系人的应用程序 我也是一名自学成才的程序员 所以我在某些方面有编程经验 但总体来说我对数据绑定相对较新 首先 我有一个 ListView 控件 其中包含图像绑定
  • 每次调用新方法时触发事件

    我正在做一个logger for a c 应用程序需要记录每个方法被调用的时间以及每个方法执行时间 我可以通过调用自己的方法来做到这一点EventLogger LogMethodCall方法在每个方法的开头 但我想知道是否有办法使CLR每次
  • 使用预编译头减少 clang 编译时间

    我正在开发一个数据库项目 该项目将查询 以某种高级语言表示 编译为 C 代码 这段代码由数据库编译并执行 那部分工作得很好 现在 我正在尝试减少 C 查询代码的编译时间 我想知道是否可以使用预编译头来提高性能 该查询被转换为一个名为 Que
  • 代码块 power 函数在 c 中不起作用

    我正在使用代码块来学习c 我的代码是 include
  • 操作/Lambda 表达式内存管理问题

    我将一个操作存储在局部变量中 然后在该局部变量超出范围后使用 使用前是否有被清理的危险 这是一个例子 public List GetMaps Action
  • 将 Python 控制台集成到 GUI C++ 应用程序中

    I m going to add a python console widget into a C GUI below some other controls 许多类将暴露给 python 代码 包括一些对 GUI 的访问 也许我会考虑 P
  • C++:初始化静态字符串成员

    我在 C 中初始化静态字符串成员时遇到一些问题 我有几个类 每个类都包含几个表示 id 的静态字符串成员 当我通过调用静态函数初始化变量时 一切都很好 但是 当我想为一个变量分配另一个变量的值时 它仍然保留空字符串 这段代码有什么问题 st
  • 本地主机上的 .net HTTP_X_FORWARDED_FOR NULL

    抱歉 如果其他地方已经回答了这个问题 我找不到它 如果没有 我会尝试查找访问过该站点的机器的原始 IP 根据我的基本理解 变量HTTP X FORWARDED FOR无论代理和其他过滤器如何 都会显示用户的 IP 如果这是真的 我正在尝试对
  • 使用 INotifyPropertyChanged

    有人可以解释一下为什么在 wpf 中使用绑定时需要使用 INotifyPropertyChanged 的 实现吗 我可以在不实现此接口的情况下绑定属性吗 例如我有代码 public class StudentData INotifyProp
  • 使用宏计算源文件行数?

    是否可以使用 C C 预处理器将源文件中的行数计算为宏或某种编译时可用值 例如 我可以更换吗MAGIC1 MAGIC2 and MAGIC3在下面 并在使用时以某种方式获取值 4MAGIC3 MAGIC1 can be placed whe
  • printf() 使用字符串表“解码器环”调试库

    我写这封信是想看看你们中是否有人见过或听说过我即将描述的想法的实现 我有兴趣为嵌入式目标开发 printf 风格的调试库 目标非常遥远 并且我和目标之间的通信带宽预算非常紧张 因此我希望能够以非常有效的格式获取调试消息 通常 调试语句如下所
  • 该组件没有由 uri 标识的资源

    我想创建一个通用数据网格以在我的所有视图 用户控件上使用 这是我的结构 Class Library called Core Class called ViewBase public class ViewBase UserControl pu
  • TreeView:仅在子节点中存在复选框

    我需要一个树视图控件 根节点没有复选框 只有图像 所有子节点都有一个复选框 图像 C net 2 0 winforms 不是 wpf WinForms树视图默认不支持混合复选框 非复选框节点 您可以在树视图上全局启用复选框 并使用以下命令在
  • 参数数量在编译时确定的 Lambda 函数

    我想声明一个带有 N 个参数的 lambda 函数 其中 N 是模板参数 就像是 template
  • 在 C# WinForms 中预览文档(Word、Excel、PDF、文本文件等)?

    我正在开发一个 C WinForms 应用程序 我希望能够 预览 其中的各种文档类型 也就是说 当用户从列表中选择文件名时 它会在下面以相同的形式显示所选文件的预览 这很像 Outlook 允许您无需双击即可预览选定邮件的方式 有没有什么方
  • 扔掉挥发物安全吗?

    大多数时候 我都是这样做的 class a public a i 100 OK delete int j Compiler happy But is it safe The following code will lead compilat
  • 从 STL 列表中删除项目

    我想创建一个函数 如果符合特定条件 则将项目从一个 STL 列表移动到另一个列表 这段代码不是这样做的方法 迭代器很可能会被擦除 函数失效并导致问题 for std list

随机推荐

  • Endnote 与word关联

    适用于endnotex7 endnotex8 endnotex9和office2019 office2021 第一步 打开Word 选择 选项 单击转到下一页 第二步 选择 加载项 COM加载项 转到 进入下一页 第三步 添加 可用加载项
  • python中.find函数的使用方法及实例_Python

    re findall findall string pos endpos 在字符串中找到正则表达式所匹配的所有子串 并返回一个列表 如果没有找到匹配的 则返回空列表 string 待匹配的字符串 pos 可选参数 指定字符串的起始位置 默认
  • [从零开始学DeepFaceLab-7]: 使用-命令行八大操作步骤-第4步:从目标图片中提取所需图片

    目录 总体流程 步骤4 从源片中提取脸部图片 4 1 命令 4 data src faceset extract MANUAL bat 不推荐使用
  • ElementUI浅尝辄止25:MessageBox 弹框

    模拟系统的消息提示框而实现的一套模态对话框组件 用于消息提示 确认消息和提交内容 从场景上说 MessageBox 的作用是美化系统自带的 alert confirm 和 prompt 因此适合展示较为简单的内容 如果需要弹出较为复杂的内容
  • 清华大学开源软件镜像站网址

    清华大学 TUNA 协会原名清华大学学生网管会 注册名清华大学学生网络与开源软件协会 是由清华大学网络技术和开源软件爱好者 技术宅组成的团体 现阶段向校内外提供开源软件镜像等服务 清华大学 TUNA 协会清华大学 TUNA 协会原名清华大学
  • win7安装了vc++6.0打开已保存文件项目就会崩溃

    我用win7安装了vc 6 0的英文完整版 绿色中文版 发现当运行程序时 要打开已保存文件项目就会崩溃 系统对话筐就说 Microsoft R Developer Studio已停止工作 选择调试或者关闭 office 2010 与vc 6
  • C++ 中只能在堆或栈上创建的对象

    1 只能在堆上创建的对象 1 把析构函数声明为private 2 定义一个destroy 函数 用这个函数来delete对象 void destroy delete this 2 只能在栈上创建的对象 1 覆盖operator new 和
  • 区块链数据不可篡改的详细解释

    区块链数据不可篡改的详细解释 背景介绍 本人新人一枚 学习区块链的过程中 在网上看到了很多讨论区块链区块数据不可篡改的文章 以比特币为例哈 主要存在2种解释 解释1 由于哈希指针的存在 假设存在某节点修改的了当前区块数据 带来的后果就是其后
  • 力扣 --- 45. 跳跃游戏II

    45 跳跃游戏II 2020 05 04 22 58 题目描述 给定一个非负整数数组 你最初位于数组的第一个位置 数组中的每个元素代表你在该位置可以跳跃的最大长度 你的目标是使用最少的跳跃次数到达数组的最后一次位置 示例 输入 2 3 1
  • vue组件(个人学习笔记三)

    目录 友情提醒 第一章 vue的组件 1 1 什么是SPA应用 1 2 vue的组件简介 1 3 vue工程中的main js文件 第二章 Vue组件的使用 2 1 一般组件的自定义 2 2 注册组件 全局注册和局部注册 2 2 1 全局注
  • phpstorm 调试_PhpStorm中的多用户调试

    phpstorm 调试 by Ray Naldo 雷 纳尔多 Ray Naldo PhpStorm中的多用户调试 Multi User Debugging in PhpStorm 使用Xdebug和DBGp代理 Using Xdebug a
  • [转](四)在 GitHub 上创建仓库

    终于我们到了最激动人心的时刻了 在 GitHub 上创建第一个仓库 下面 我们通过一次上传 Github 的完整操作 实践学习 Git 的常用功能 首先 申请一个 Github 账户 打开 GitHub 你可以在主页的 banner 上快速
  • 华为OD机试 Python 【跳房子II】

    描述 跳房子 是个儿童游戏 你得跳过一排房子 从第一个直到最后一个 成功跳完一轮 你可以选择一个房子 当所有房子都被选了 拥有最多房子的人就赢了 如果你踩线或犯规 你这轮就结束 可能还得倒退 假设有count个房子格子 小红每轮可以选择跳一
  • 调整线程池对性能影响

    默认最小线程数是CPU的内核数 默认最大线程数是机器内核数的250倍 线程池调度会将激活的线程限制在默认最小线程数 如果没有线程结束的话每秒至多可以唤起两个新的线程 假设一个四核的机器 对于线程池来说 会运行很久或很多堵塞的不是I O引起的
  • 创建 WinForm 应用程序

    创建 WinForm 应用程序 创建 WinForm 应用程序 创建 WinForm 项目 点击 文件 gt 新建 gt 项目 选项 进入 新建项目 界面 选中 Windows窗体 应用程序 并设置项目的名称 位置及解决方案名称 如下图所示
  • JavaScript预编译过程

    JavaScript预编译过程 阶段 三个 预编译过程 1 JavaScript代码执行之前的预编译 案例说明 2 函数执行前的预编译 案例说明 总结 预编译两个小规则 预编译前奏 阶段 三个 词法语法分析 词法语法分析就是检查JavaSc
  • Linux中找不到blas库,linux – caffe:/usr/bin/ld:找不到-lcblas

    我已经在我的CentOS7 64位 中安装了BLAS 但是当我的使用全部在我的 caffe 它报告了一个错误 usr bin ld cannot find lcblas usr bin ld cannot find latlas colle
  • MySql创建新用户并赋予某些表的读写权限

    1 登录root用户 2 创建一个新用户 CREATE USER 用户名 IDENTIFIED BY 密码 3 赋予该用户相应权限 GRANT SELECT INSERT UPDATE DELETE ON 库名 表名 TO 用户名
  • 已解决No suitable driver found for jdbc:mysql://localhost:3306/ 问题

    已解决No suitable driver found for jdbc mysql localhost 3306 问题 本文目录 一 Bug描述 二 定位报错点及原因 三 最终的解决方案 四 相关注意事项 总结 一 Bug描述 在学习ja
  • Acwing-4653. 数位排序

    本题重点在于预处理每个数的各位之和 cmp函数的书写 根据题目中的描述 当两个数各个数位之和不同时 将数位和较小的排在前面 当数位之和相等时 将数值小的排在前面 不难写出cmp函数 快速排序的比较次数为nlogn次 本题中约为2 10 7