草庐IT

c++ - 给定数字 N 消除 K 数字以获得最大可能数字

coder 2024-02-03 原文

正如标题所说，任务是:

给定号码N消除 K数字以获得最大可能的数字。数字必须保持原位。

示例:n = 12345 , k = 3 , max = 45 (前三位数字被删除，数字不得移动到另一个位置)。

知道如何解决这个问题吗？
(不是作业，我是准备算法大赛，在线评委上解题。)

1 <= N <= 2^60 , 1 <= K <= 20 .

编辑:这是我的解决方案。它正在工作:)

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;


int main()
{
    string n;
    int k;

    cin >> n >> k;

    int b = n.size() - k - 1;
    int c = n.size() - b;
    int ind = 0;
    vector<char> res;
    char max = n.at(0);

    for (int i=0; i<n.size() && res.size() < n.size()-k; i++) {
        max = n.at(i);
        ind = i;
        for (int j=i; j<i+c; j++) {
            if (n.at(j) > max) {
                max = n.at(j);
                ind = j;
            }
        }

        b--;
        c = n.size() - 1 - ind - b;
        res.push_back(max);
        i = ind;
    }

for (int i=0; i<res.size(); i++)
    cout << res.at(i);

cout << endl;

    return 0;
}

最佳答案

对于您的限制，暴力破解应该足够快:n 最多有 19 位。生成所有具有 numDigits(n) 位的正整数。如果设置了k位，则删除与设置位对应的位置的数字。将结果与全局最优值进行比较，并在需要时进行更新。

复杂度:O(2^log n * log n)。虽然这可能看起来很多并且与 O(n) 渐近地相同，但实际上它会快得多，因为 O(2^log n * log n 中的对数) 是一个以 10 为底的对数，它将给出一个小得多的值(1 + log base 10 of n 给你 的位数n).

您可以通过每次生成 n - k 的 n 组合并构建由以下组成的数字来避免 log n 因子生成每个组合时选择的 n - k 位置(将其作为参数传递)。这基本上意味着您解决了类似的问题:给定 n，按顺序选择 n - k 位数字，使得结果数最大)。

注意:有一种不涉及暴力破解的方法可以解决这个问题，但我也想向 OP 展示这个解决方案，因为他在评论中询问如何使用暴力破解.对于最佳方法，研究如果我们从左到右逐位构建我们的数字会发生什么，并且对于每个数字 d，我们将删除所有当前选择的小于它的数字。我们什么时候可以删除它们，什么时候不能？

关于c++ - 给定数字 N 消除 K 数字以获得最大可能数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21631751/

给定ampcodesectionltc++algorithm

有关c++ - 给定数字 N 消除 K 数字以获得最大可能数字的更多相关文章

  1. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 无法在 60 秒内获得稳定的 Firefox 连接 (127.0.0.1 :7055) - 2

    我使用的是Firefox版本36.0.1和Selenium-Webdrivergem版本2.45.0。我能够创建Firefox实例，但无法使用脚本继续进行进一步的操作无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)错误。有人能帮帮我吗？ 最佳答案 我遇到了同样的问题。降级到firefoxv33后一切正常。您可以找到旧版本here 关于ruby-无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)，我们在StackOverflow上找到一个类

  4. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  5. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  6. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. ruby - 将n维数组的每个元素乘以Ruby中的数字 - 2

    在Ruby中，是否有一种简单的方法可以将n维数组中的每个元素乘以一个数字？这样:[1,2,3,4,5].multiplied_by2==[2,4,6,8,10]和[[1,2,3],[1,2,3]].multiplied_by2==[[2,4,6],[2,4,6]]？(很明显，我编写了multiplied_by函数以区别于*，它似乎连接了数组的多个副本，不幸的是这不是我需要的)。谢谢! 最佳答案 它的长格式等价物是:[1,2,3,4,5].collect{|n|n*2}其实并没有那么复杂。你总是可以使你的multiply_by方法:c

  9. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  10. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

随机推荐