c++ - 找出将景观淹没到一定体积所需的水高

coder 2024-02-20 原文

我最近遇到了一个算法问题，其目标是计算在建筑物宽度为 1 的城市中产生一定量洪水所需的水位高度。

这有点类似于此处描述的二维雨水收集问题:

The Maximum Volume of Trapped Rain Water in 3D

但是，在我的问题中，除了建筑物之间的积水之外，我们还计算了建筑物上方的水。例如，以这个问题为例:

volume needed: 60
number of buildings: 3
heights of buildings: 30 40 20

这意味着我们必须计算所需的水位，这样一座建筑物高度为 30、40 和 20 的城市(按此顺序)就会有至少 60 的洪水。

^
|
50       |~~~~~~~~~~~~~|
|        |             |        
40       |    -----    |                
|        |    |   |    |                 
30       -----|   |    |               
|        |   ||   |    |        
20       |   ||   |-----
|        |   ||   ||   |
10       |   ||   ||   |
|        |   ||   ||   |
.----------1----2----3---------->

在这种情况下，结果将为 50，因为水位需要处于 50 高度，这样建筑物之间和建筑物上方的水量至少为 60。这里，每栋建筑物上方的洪水为 20、10、和 30，加起来正好是 60。

我的尝试在时间和正确性上都表现不佳:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int v;
  int n;
  cin >> v >> n;

  vector<int> altitudes;
  int count = 0;
  int altitude;

  while (count < n) {
    cin >> altitude;
    altitudes.push_back(altitude);
    count++;
  }

  sort(altitudes.begin(), altitudes.end());

  int vtemp = 0;
  int i = 1;
  int h = altitudes[0];

  while (vtemp < v && i < n) {
    h++;
    if (h == altitudes[i]) {
      i++;
    }
    vtemp = 0;
    for (int j = 0; j < i; j++) {
      vtemp += h - altitudes[j];
    }
  }

  cout << h << endl;

  return 0;
}

最佳答案

我在代码中为我的算法添加了注释。我在您的测试数据上对其进行了测试，并且可以正常工作。时间复杂度是 O(n log n) 因为我们需要对建筑物进行排序。没有排序算法在 O(n) 中工作

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int v;
    int n;
    cin >> v >> n;

    vector<int> altitudes;
    int count = 0;
    int altitude;

    while (count < n) {
        cin >> altitude;
        altitudes.push_back(altitude);
        count++;
    }

    sort(altitudes.begin(), altitudes.end());
//-- changed from here
    int current_level = altitudes[0]; //start from height of the smallest building
    int length = 0;

    while (v > 0)
    {
        ++length; //go to next level
        for (; length < altitudes.size() && altitudes[length] == altitudes[length - 1]; ++length); //find length of current water level

        int height = v / length; //maximum possible height to fill
        if (length < altitudes.size()) //if not all building in use
            height = min(height, altitudes[length] - current_level); //fill with all water (height) or with the difference to next level

        current_level += height; //increase level by height
        v -= height * length; //decrease amount of water

        if (length == altitudes.size() || v < length) //we filled the whole area, or there is no enough water to fill 1 'meter'
            break;
    }

    cout << current_level << endl;

    return 0;
}

关于c++ - 找出将景观淹没到一定体积所需的水高，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34484682/

amp 景观 altitudes length int c++algorithm

有关c++ - 找出将景观淹没到一定体积所需的水高的更多相关文章

ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
ruby - 匹配大写字母并用后续字母填充，直到一定的字符串长度 - 2
我有一个驼峰式字符串，例如:JustAString。我想按照以下规则形成长度为4的字符串:抓取所有大写字母；如果超过4个大写字母，只保留前4个；如果少于4个大写字母，则将最后大写字母后的字母大写并添加字母，直到长度变为4。以下是可能发生的3种情况:ThisIsMyString将产生TIMS(大写字母)；ThisIsOneVeryLongString将产生TIOV(前4个大写字母)；MyString将生成MSTR(大写字母+tr大写)。我设法用这个片段解决了前两种情况:str.scan(/[A-Z]/).first(4).join但是，我不太确定如何最好地修改上面的代码片段以处理最后一种
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.你能做的最好的事情是:
ruby - 如何计算 Liquid 中的变量 +1 - 2
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。最佳答案因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
即使安装了 gem，Ruby 也找不到所需的库 - 2
我花了几天时间尝试安装ruby1.9.2并让它与gems一起工作:-/我最终放弃了我的MacOSX10.6机器，下面是我的Ubuntu机器上的当前状态。任何建议将不胜感激!#rubytest.rb:29:in`require':nosuchfiletoload--mongo(LoadError)from:29:in`require'fromtest.rb:1:in`'#cattest.rbrequire'mongo'db=Mongo::Connection.new.db("mydb")#gemwhichmongo/usr/local/rvm/gems/ruby-1.9.2-p0/g
ruby - Rails -- :id attribute? 所需的数据库索引 - 2
因此，当我遵循MichaelHartl的RubyonRails教程时，我注意到在用户表中，我们为:email属性添加了一个唯一索引，以提高find的效率方法，因此它不会逐行搜索。到目前为止，我们一直在根据情况使用find_by_email和find_by_id进行搜索。然而，我们从未为:id属性设置索引。:id是否自动索引，因为它在默认情况下是唯一的并且本质上是顺序的？或者情况并非如此，我应该为:id搜索添加索引吗？最佳答案大多数数据库(包括sqlite，这是RoR中的默认数据库)会自动索引主键，对于RailsMigration
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”]、[“苹果”、“
ruby-on-rails - 如何找出拦截 'method_missing' 的内容 - 2
使用Ruby1.8.6/Rails2.3.2我注意到在我的任何ActiveRecord模型类上调用的任何方法都返回nil而不是NoMethodError。除了烦人之外，这还破坏了动态查找器(find_by_name、find_by_id等)，因为即使存在记录，它们也总是返回nil。不从ActiveRecord::Base派生的标准类不受影响。有没有办法追踪在ActiveRecord::Base之前拦截method_missing的是什么？更新:切换到1.8.7后，我发现(感谢@MichaelKohl)will_paginate插件首先处理method_missing。但是will_pa
+= 的 Ruby 方法 - 2
有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=
ruby - TypeError(救援条款所需的类或模块) - 2
我已经使用Stripe一年多了，基于RyanBates的RailsCast插曲发现here.但是，我的错误处理最近停止工作，而且我以前从未见过此错误。我最近开始在Ruby2.1上运行我的应用程序，据我所知，这就是问题所在。这是我的订阅模型中的一个实例方法:beginsave_with_stripe_paymentrescueStripe::InvalidRequestError=>elogger.error"Stripeerrorwhilecreatingcustomer:#{e.message}"logger.errore.backtrace.join("\n")errors.add

c++ - 找出将景观淹没到一定体积所需的水高

有关c++ - 找出将景观淹没到一定体积所需的水高的更多相关文章

随机推荐