acwing第 115 场周赛第二题题解:维护最大值和次大值

一、链接

5132. 奶牛照相

二、题目

约翰的农场有 nn 头奶牛,编号 1∼n1∼n。

其中,第 ii 头奶牛的宽度为 wiwi,高度为 hihi,

有一天,它们聚餐后决定拍照留念。

关于拍照的描述如下:

  • 它们一共拍了 nn 张照片,其中第 ii 张照片由第 ii 头奶牛给其它所有奶牛拍摄,即照片中包含除了奶牛 ii 以外的所有奶牛。
  • 在拍照时,所有被拍摄的奶牛站成一排,拍出的照片呈矩形。
  • 每张照片的尺寸大小为 W×HW×H,其中 WW 为照片中所有奶牛的宽度之和,HH 为照片中最高的奶牛的高度。

请你计算并输出每张照片的面积(W×HW×H 的值)。

输入格式

第一行包含整数 nn,表示共有 nn 头奶牛。

接下来 nn 行,其中第 ii 行包含两个整数 wi,hiwi,hi,表示第 ii 头奶牛的宽度和高度。

输出格式

输出共一行,nn 个整数,其中第 ii 个整数表示第 ii 张照片的面积。

注意,第 ii 张照片包含除了奶牛 ii 以外的所有奶牛

数据范围

前 33 个测试点满足 2≤n≤32≤n≤3。
所有测试点满足 2≤n≤2×1052≤n≤2×105,1≤wi≤101≤wi≤10,1≤hi≤10001≤hi≤1000。

输入样例1:

3
1 10
5 5
10 1

输出样例1:

75 110 60

输入样例2:

3
2 1
1 2
2 1

输出样例2:

6 4 6

三、题意

去除某一个元素,其他元素的宽度求和,高度取最大值,输出乘积

四、代码

#include<iostream>
#include<algorithm>using namespace std;const int N=2e5+10;int w[N],h[N];int main()
{int n,sum=0,h1=0,h2=0,res=0;scanf("%d",&n);for(int i=0;i<n;i++)    {scanf("%d%d",&w[i],&h[i]);sum+=w[i];if(h[i]>h1) h2=h1,h1=h[i];else if(h[i]>h2)    h2=h[i];}for(int i=0;i<n;i++){if(h[i]==h1){res=(sum-w[i])*h2;}else{res=(sum-w[i])*h1;}printf("%d ",res);}return 0;
}

五、总结

1.不要单纯的模拟,不是很熟练,单纯的模拟比较难以实现,要想办法怎么写能达到同样的要求

2.求和比较简单,先求出所有元素宽度的和,然后每一个循环减去当前元素的宽度,就是去除当前元素的和

3.求去除一个元素之后的高度的最大值,有两种情况,第一种情况,去除的元素的高度是最大值(针对所有元素来说),那么就需要使用次大值(所有元素的次大值),第二种情况,去除的元素的高度不是最大值(针对所有元素来说),就使用最大值即可

4.在初始化阶段求出高度的最大值和次大值:次大值小于等于最大值,可以把数轴分成三个区间第一个区间是遍历的元素大于最大值,把次大值更新为原来的最大值,把最大值更新成当前遍历的元素第二个区间是在次大值和最大值之间,最大值不变,次大值更新为当前元素第三个区间是当前元素小于次大值,最大值和次大值不需要进行修改

5.输出结果这道题就完美的ac了

六、精美图片

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79637.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux初阶】基础IO - 动静态库 | 初识、生成、链接、加载

&#x1f31f;hello&#xff0c;各位读者大大们你们好呀&#x1f31f; &#x1f36d;&#x1f36d;系列专栏&#xff1a;【Linux初阶】 ✒️✒️本篇内容&#xff1a;动静态库初识&#xff0c;库的含义&#xff0c;静态库的生成与链接&#xff0c;gcc/g默认链接方式&#xff0c…

Grafana V10 告警推送

最近项目建设完成&#xff0c;一个城域网项目&#xff0c;相关zabbix和grafana展示已经完&#xff0c;想了想&#xff0c;不想天天看平台去盯网络监控平台&#xff0c;索性对告警进行分类调整&#xff0c;增加告警的推送&#xff0c;和相关部门的提醒&#xff0c;其他部门看不懂…

C语言经典小游戏之三子棋(超详解释+源码)

“纵有疾风来&#xff0c;人生不言弃&#xff0c;风乍起&#xff0c;合当奋意向此生。” 今天我们一起来学习一下三子棋小游戏用C语言怎么写出来&#xff1f; 三子棋小游戏 1.游戏规则介绍2.游戏准备3.游戏的实现3.1生成菜单3.2游戏的具体实现3.2.1初始化棋盘3.2.2打印棋盘3.2…

rv1109/1126 rknn 模型部署过程

rv1109/1126是瑞芯微出的嵌入式AI芯片&#xff0c;带有npu, 可以用于嵌入式人工智能应用。算法工程师训练出的算法要部署到芯片上&#xff0c;需要经过模型转换和量化&#xff0c;下面记录一下整个过程。 量化环境 模型量化需要安装rk的工具包&#xff1a; rockchip-linux/rk…

FineBI 人力资源 专题

此处使用FineBI处理人力资源数据&#xff0c;数据来源于HR_database数据文件&#xff0c;将此文件拷贝到安装目录下 然后配置数据库连接 在【公共数据】中新建一个文件夹&#xff0c;并将之前数据库中需要用到的表放入此处&#xff0c;更新数据。显示如下。 这时候首先要建立…

Flutter 自定义view

带进度动画的圆环。没gif&#xff0c;效果大家自行脑补。 继承CustomPainter&#xff0c;paint()方法中拿到canvas&#xff0c;绘制API和android差不多。 import package:flutter/material.dart;class ProgressRingPainter extends CustomPainter {double strokeWidth 20;Col…

【网络技术】TCP详解

1 TCP是什么 TCP是Transmission Control Protocol的缩写&#xff0c;即传输控制协议。 TCP是一种面向连接的、可靠的、基于字节流的传输协议&#xff0c;是互联网通信协议TCP/IP中的一个重要组成部分。 2 三次握手 三次握手的过程可以用以下图示表示&#xff1a; 2.1 详细介绍…

《算法竞赛·快冲300题》每日一题:“连接草坪(II)”

《算法竞赛快冲300题》将于2024年出版&#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码&#xff0c;以中低档题为主&#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 连…

[Docker实现测试部署CI/CD----自由风格的CI操作[中间架构](4)]

目录 10、自由风格的CI操作&#xff08;中间架构&#xff09;中间架构图创建web项目Idea提交项目到远程仓库提交代码到本地库提交代码到远程库从jenkins拉取代码新建任务jenkins集成gitlab立即构建 将项目打为jar包Jenkins 配置 mvn 命令重新构建 代码质量检测jenkins将代码推送…

HTTP(超文本传输协议)学习

关于HTTP补学 一、HTTP能干什么 通过下图能够直观的看出&#xff1a;“交换数据 ” 二、HTTP请求例子 一个 HTTP 方法&#xff0c;通常是由一个动词&#xff0c;像 GET、POST 等&#xff0c;或者一个名词&#xff0c;像 OPTIONS、HEAD 等&#xff0c;来定义客户端执行的动作。…

小学语文思维导图:如何写一篇好的作文

大家都知道&#xff0c;思维导图是一款非常高效的工具。我们利用思维导图不仅可以做读书笔记、还可以运用到很多具体细分的场景。今天我们就“如何利用思维导图写好一篇作文”和大家进行分享。 思维导图在写作文的过程中&#xff0c;可以帮助我们整理思路。提高效率。将混乱的内…

【iOS安全】OpenSSH使用

安装OpenSSH 在 Cydia 中直接查找和安装 OpenSSH 使用OpenSSH http://orinchen.github.io/blog/2014/01/15/install-and-use-openssh-on-ios/ 保证PC和iPhone在同一网段下 查看iPhone的IP地址 ssh root10.168.xx.xx 口令默认是alpine 或者也可以使用XShell等集成终端

再次斩获第一,文心3.5霸榜国内大模型

目录 1 什么是文心一言&#xff1f;2 体验与文心一言对话3 文心3.5霸榜国内大模型 1 什么是文心一言&#xff1f; 文心一言是百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xf…

数据结构--单链表OJ题

上文回顾---单链表 这章将来做一些链表的相关题目。 目录 1.移除链表元素 2.反转链表 3.链表的中间结点 4.链表中的倒数第k个结点 5.合并两个有序链表 6.链表分割 7.链表的回文结构 8.相交链表 9.环形链表 ​编辑 10.环形链表II ​编辑 ​编辑 1.移除链表元素 思…

2023暑假牛客多校6- E.Sequence

题目描述 You have an array of elements . For each task, you have three integers . Ask whether you can find an array of integers satisfy: are the multiplies of 2 Specially, if , it should satisfy is the multiply of 2 We define . If possible, print…

Java课题笔记~ 动态SQL详解

一、动态 sql 是什么&#xff1f; 1、动态 SQL 是 MyBatis 的强大特性之一。在 JDBC 或其它类似的框架中&#xff0c;开发人员通常需要手动拼接 SQL 语句。根据不同的条件拼接 SQL 语句是一件极其痛苦的工作。 例如&#xff0c;拼接时要确保添加了必要的空格&#xff0c;还要…

cnvd通用型证书获取姿势

因为技术有限&#xff0c;只能挖挖不用脑子的漏洞&#xff0c;平时工作摸鱼的时候通过谷歌引擎引擎搜索找找有没有大点的公司有sql注入漏洞&#xff0c;找的方法就很简单&#xff0c;网站结尾加上’&#xff0c;有异常就测试看看&#xff0c;没有马上下一家&#xff0c;效率至上…

Day12-1-Webpack前端工程化开发

Webpack前端工程化 1 案例-webpack打包js文件 1 在index.html中编写代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><me…

20天学会rust(二)rust的基础语法篇

在第一节&#xff08;20天学rust&#xff08;一&#xff09;和rust say hi&#xff09;我们配置好了rust的环境&#xff0c;并且运行了一个简单的demo——practice-01&#xff0c;接下来我们将从示例入手&#xff0c;学习rust的基础语法。 首先来看下项目结构&#xff1a; 项目…

QtWebApp开发https服务器,完成客户端与服务器基于ssl的双向认证,纯代码操作

引言&#xff1a;所谓http协议&#xff0c;本质上也是基于TCP/IP上服务器与客户端请求和应答的标准&#xff0c;web开发中常用的http server有apache和nginx。Qt程序作为http client可以使用QNetworkAccessManager很方便的进行http相关的操作。Qt本身并没有http server相关的库…