草庐IT

c++ - 这个程序的复杂度是多少

coder 2024-02-24 原文

我在 HackerEarth 上解决了一个问题。 问题是

Phineas 正在他的后院 build 一座城堡来打动 Isabella(很奇怪，不是吗？)。他已经把所有东西都准备好了。甚至一楼也已经完工。现在是时候制作上半部分了。这就是事情变得有趣的地方。由于 Ferb 在粉刷栅栏一整天后正在屋子里 sleep (你们帮了他，不是吗!)，Phineas 必须自己完成所有工作。他很擅长这个，他要你做的就是操作迷你起重机来吊起石头。围墙的石头已经切割好了，等着你去搬。

现在我们没有 Ferb 来操作小型起重机，他是这方面的专家，我们必须尽快完成这项工作。我们给出了起重机的最大起重能力，以及每 block 石头的重量。由于它是一台小型起重机，我们不能一次放置超过 2 block 石头(任何可能的大小)，否则会扰乱起重机的平衡。我们需要找出在多少圈内我们可以将石头运送给正在 build 城堡的菲尼亚斯。

INPUT:输入的第一行给出 T，测试用例的数量。对于每个测试用例，第一行给出起重机的最大起重能力 M。每个测试用例下一行的第一个整数 N 给出石子的数量，然后是 N 个数字，指定单个石子 X 的重量。

输出:对于每个测试用例，打印吊车运行所有待提升石头的最小转数。

约束:

1 <= T <= 50
1 <= M <= 1000
1 <= N <= 1000

示例输入

1
50
3 28 22 48

示例输出

2

解释 第一回合，28 和 22 将一起举起。在第二轮 48 将被解除。 丢弃重量 > 起重机最大容量的石头。

现在我已经解决了这个问题，我的源代码是

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;


int main(void) {
    int T = 0;
    scanf("%d",&T);
    while(T--) {
        int i = 0,M = 0, N = 0,max = 0, res = 0, index = 0, j = 0, temp = 0;
        vector<int> v1;
        scanf("%d",&M);
        scanf("%d",&N);
        for(i = 0; i < N ;++i) {
            scanf("%d",&temp);
            if(temp <= M)
                v1.push_back(temp);
        }

        for(i = 0; i < v1.size() ; ++i) {
            max = 0;
            index = 0;
            if(v1[i] != -1) {
                for(j = i + 1; j < v1.size(); ++j) {
                    if(v1[j] != -1) {
                        temp = v1[i] + v1[j];
                        if(temp > max && temp <= M) {
                            max = temp;
                            index = j;
                        }
                    }
                }
                ++res;
                v1[i] = -1;
                v1[index] = -1;
            }
        }

        printf("%d\n",res);
    }

    return 0;

}

这是我的问题

  1. 我想知道这段代码的平均用例时间复杂度。此外，我认为这段代码的最坏情况复杂度为 O(N^2)。
  2. 这是蛮力法还是动态规划法？
  3. 还有比这更好的方法吗？

最佳答案

这是 Knapsack Prolblem 的简化版本

虽然背包问题是典型的动态规划问题，但这个简化的问题不需要动态规划。您的解决方案的复杂性确实是 O(n^2)，该方法更适合描述为 Greedy当您尝试为每颗 gem 找到最佳配对时(如果存在)。如果先对石头进行排序并处理排序后的 vector ，则复杂度可以进一步降低到 O(nlgn)。

关于c++ - 这个程序的复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28362323/

amp43起重起重机sectionc++algorithmcomplexity-theory

有关c++ - 这个程序的复杂度是多少的更多相关文章

  1. ruby - 在 Ruby 程序执行时阻止 Windows 7 PC 进入休眠状态 - 2

    我需要在客户计算机上运行Ruby应用程序。通常需要几天才能完成(复制大备份文件)。问题是如果启用sleep，它会中断应用程序。否则，计算机将持续运行数周，直到我下次访问为止。有什么方法可以防止执行期间休眠并让Windows在执行后休眠吗？欢迎任何疯狂的想法;-) 最佳答案 Here建议使用SetThreadExecutionStateWinAPI函数，使应用程序能够通知系统它正在使用中，从而防止系统在应用程序运行时进入休眠状态或关闭显示。像这样的东西:require'Win32API'ES_AWAYMODE_REQUIRED=0x0

  2. ruby - 如何指定 Rack 处理程序 - 2

    Rackup通过Rack的默认处理程序成功运行任何Rack应用程序。例如:classRackAppdefcall(environment)['200',{'Content-Type'=>'text/html'},["Helloworld"]]endendrunRackApp.new但是当最后一行更改为使用Rack的内置CGI处理程序时，rackup给出“NoMethodErrorat/undefinedmethod`call'fornil:NilClass”:Rack::Handler::CGI.runRackApp.newRack的其他内置处理程序也提出了同样的反对意见。例如Rack

  3. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  4. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  5. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

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

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

  7. ruby-on-rails - Rails 应用程序中的 Rails : How are you using application_controller. rb 是新手吗？ - 2

    刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr

  8. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

  9. ruby - 可以通过多少种方法将方法添加到 ruby​​ 对象？ - 2

    当谈到运行时自省(introspection)和动态代码生成时，我认为ruby​​没有任何竞争对手，可能除了一些lisp方言。前几天，我正在做一些代码练习来探索ruby​​的动态功能，我开始想知道如何向现有对象添加方法。以下是我能想到的3种方法:obj=Object.new#addamethoddirectlydefobj.new_method...end#addamethodindirectlywiththesingletonclassclass这只是冰山一角，因为我还没有探索instance_eval、module_eval和define_method的各种组合。是否有在线/离线资

  10. ruby - 检查是否通过 require 执行或导入了 Ruby 程序 - 2

    如何检查Ruby文件是否是通过“require”或“load”导入的，而不是简单地从命令行执行的？例如:foo.rb的内容:puts"Hello"bar.rb的内容require'foo'输出:$./foo.rbHello$./bar.rbHello基本上，我想调用bar.rb以不执行puts调用。 最佳答案 将foo.rb改为:if__FILE__==$0puts"Hello"end检查__FILE__-当前ruby​​文件的名称-与$0-正在运行的脚本的名称。 关于ruby-检查是否

随机推荐