草庐IT

「贪心&优先队列」数列极差

孤星·璀璨 2023-03-28 原文

本题为1月3日22寒假集训每日一题题解

题目来源:(未知)

题面

题目描述

佳佳的老师在黑板上写了一个由n个正整数组成的数列，要求佳佳进行如下操作：每次擦去其中的两个数a和b，然后在数列中加入一个数 $ a * b + 1 $ ，如此下去直至黑板上剩下一个数为止，在所有按这种操作方式最后得到的数中，最大的为max，最小的为 min， 则该数列的极差定义为$ M=max−min $。

由于佳佳忙于准备期末考试，现请你帮助他，对于给定的数列，计算出相应的极差M。

输入

第一行为一个正整数n表示正整数序列的长度；

在接下来的n行中，每行输入一个正整数。

接下来的一行有一个0，表示数据结束。

输出

输出只有一行，为相应的极差d。

样例输入

3
1
2
3
0

样例输出

2

提示

对于全部数据，0≤n≤50000，保证所有数据计算均在32位有符号整数范围内。

思路分析

首先观察3个数的情况,若有 $ a > b > c $,我们先后取出不同的数进行运算,情况如下:

  1. $ (a \times b + 1) \times c + 1 = a \times b \times c + c + 1 $
  2. $ (a \times c + 1) \times b + 1 = a \times b \times c + b + 1 $
  3. $ (b \times c + 1) \times a + 1 = a \times b \times c + a + 1 $

简单观察可以发现,最后取得的数的共同部分是 $ a \times b \times c $ ,以及最后的 $ + 1 $ ,不同的地方只有中间那一项,可以发现如下规律:

  • 如果先取最小两项,那么中间那一项(这一项同时也是最晚乘进去的数)就是最大项,此时结果也是最大的
  • 如果先取最大两项,那么中间那一项(这一项同时也是最晚乘进去的数)就是最小项,此时结果也是最小的

那如果是n个数呢?显然最后取出的数的组合会和上面一样,最前和最后都是相同的(所有数相乘和1),只有中间那一些不同.所以想要答案最大,就需要中间最大.显然,越后面选的数会在其中作为乘数出现更多次(位于更外层的括号,更晚乘进去),所以想要答案最大,就要每次都选最小的两个数,以让越大的数越晚选.答案最小同理,只需每次都选最大的两个数.

这就是本题的贪心策略,只要按照这个策略分别计算出最大值和最小值,然后再做差即可.由于每次都要取出当前的最小/大值,然后把计算好的结果再加入,所以我们需要借助优先队列这一数据结构(当然,每次计算后再排序也可以,但是这样效率会低一点).

参考代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    if (n <= 1) // 1个数时下面的代码不适用,不过此时极差显然为0,所以直接输出即可
    {
        cout << 0 << "\n";
        return 0;
    }

    // 两个优先队列,分别用于计算最大值(每次取出最小值,使用小顶堆)和最小值(每次取出最大值,使用大顶堆)
    priority_queue<int, vector<int>, greater<int>> queToCountMax;
    priority_queue<int> queToCountMin;

    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        queToCountMin.push(num);
        queToCountMax.push(num);
    }

    // 最大值和最小值
    int maxNum, minNum;

    // 计算最大值,每次取出两个数,然后把计算结果再插入回去
    while (queToCountMax.size() > 1)
    {
        int num = queToCountMax.top();
        queToCountMax.pop();
        num = num * queToCountMax.top() + 1;
        queToCountMax.pop();
        queToCountMax.push(num);
    }
    maxNum = queToCountMax.top();

    // 计算最小值,每次取出两个数,然后把计算结果再插入回去
    while (queToCountMin.size() > 1)
    {
        int num = queToCountMin.top();
        queToCountMin.pop();
        num = num * queToCountMin.top() + 1;
        queToCountMin.pop();
        queToCountMin.push(num);
    }
    minNum = queToCountMin.top();

    cout << maxNum - minNum << "\n";

    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德

amp贪心queToCountMaxqueToCountMintimes算法与数据结构

有关「贪心&优先队列」数列极差的更多相关文章

  1. ruby-on-rails - rails : "missing partial" when calling 'render' in RSpec test - 2

    我正在尝试测试是否存在表单。我是Rails新手。我的new.html.erb_spec.rb文件的内容是:require'spec_helper'describe"messages/new.html.erb"doit"shouldrendertheform"dorender'/messages/new.html.erb'reponse.shouldhave_form_putting_to(@message)with_submit_buttonendendView本身，new.html.erb，有代码:当我运行rspec时，它失败了:1)messages/new.html.erbshou

  2. ruby-on-rails - 由于 "wkhtmltopdf"，PDFKIT 显然无法正常工作 - 2

    我在从html页面生成PDF时遇到问题。我正在使用PDFkit。在安装它的过程中，我注意到我需要wkhtmltopdf。所以我也安装了它。我做了PDFkit的文档所说的一切......现在我在尝试加载PDF时遇到了这个错误。这里是错误:commandfailed:"/usr/local/bin/wkhtmltopdf""--margin-right""0.75in""--page-size""Letter""--margin-top""0.75in""--margin-bottom""0.75in""--encoding""UTF-8""--margin-left""0.75in""-

  3. ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2

    我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t

  4. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

  5. ruby - 检查 "command"的输出应该包含 NilClass 的意外崩溃 - 2

    为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar

  6. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

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

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

  8. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案？ - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  9. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  10. ruby - 无法让 RSpec 工作—— 'require' : cannot load such file - 2

    我花了三天的时间用头撞墙，试图弄清楚为什么简单的“rake”不能通过我的规范文件。如果您遇到这种情况:任何文件夹路径中都不要有空格!。严重地。事实上，从现在开始，您命名的任何内容都没有空格。这是我的控制台输出:(在/Users/*****/Desktop/LearningRuby/learn_ruby)$rake/Users/*******/Desktop/LearningRuby/learn_ruby/00_hello/hello_spec.rb:116:in`require':cannotloadsuchfile--hello(LoadError) 最佳

随机推荐