AcWing244. 谜一样的牛(树状数组)

输入样例:

5
1
2
1
0

输出样例:

2
4
5
3
1

 解析:

        从后往前遍历,每次需要在剩余的数中,找到第 h[ i ]+1 大的数即为当前牛的身高。

        每次二分,然后求前缀和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,m,h[N],ans[N],tr[N];
int lowbit(int x){return x&-x;
}
void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
}
int sum(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=tr[i];return ans;
}
int main(){scanf("%d",&n);for(int i=2;i<=n;i++) scanf("%lld",&h[i]);for(int i=1;i<=n;i++) add(i,1);	for(int i=n;i>0;i--){int k=h[i]+1;int l=1,r=n;while(l<r){int mid=l+r>>1;if(sum(mid)>=k) r=mid;else l=mid+1;}ans[i]=r;add(l,-1);}for(int i=1;i<=n;i++) printf("%d\n",ans[i]);return 0;
}

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

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

相关文章

回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测

回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循环单元多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SO-CNN-GRU蛇群算法优化卷积门控循…

消息队列——rabbitmq的不同工作模式

目录 Work queues 工作队列模式 Pub/Sub 订阅模式 Routing路由模式 Topics通配符模式 工作模式总结 Work queues 工作队列模式 C1和C2属于竞争关系&#xff0c;一个消息只有一个消费者可以取到。 代码部分只需要用两个消费者进程监听同一个队里即可。 两个消费者呈现竞争关…

【1.2】Java微服务:SpringCloud概论

✅作者简介&#xff1a;大家好&#xff0c;我是 Meteors., 向往着更加简洁高效的代码写法与编程方式&#xff0c;持续分享Java技术内容。 &#x1f34e;个人主页&#xff1a;Meteors.的博客 &#x1f49e;当前专栏&#xff1a; 微服务 ✨特色专栏&#xff1a; 知识分享 &#x…

纯css实现登录表单动效

效果图&#xff1a; 代码展示 // 我这边用的是elementUI表单校验&#xff0c;更改的样式。 <el-form:model"form":rules"rules"ref"fromList":hide-required-asterisk"true"><el-form-item prop"account"><…

【phaser微信抖音小游戏开发005】画布上添加图片

特别注意&#xff1a;真机模拟的时候&#xff0c;尽量使用网络图片资源&#xff0c;不要在小程序源文件里面使用图片&#xff0c;会出现真机加载不成功&#xff0c;小程序包体积过大的问题。我们学习过程中&#xff0c;只是作为演示使用。 推荐使用场景&#xff1a; 背景图片…

vue3引入video.js

一.引入video.js yarn add video.js videojs-player/vue --save 或者 npm install video.js videojs-player/vue --save 二.vue3项目main.js引入 import VueVideoPlayer from "videojs-player/vue" import "video.js/dist/video-js.css" const app cr…

W6100-EVB-PICO做DNS Client进行域名解析

前言 在上一章节中我们用W6100-EVB-PICO通过dhcp获取ip地址&#xff08;网关&#xff0c;子网掩码&#xff0c;dns服务器&#xff09;等信息&#xff0c;给我们的开发板配置网络信息&#xff0c;成功的接入网络中&#xff0c;那么本章将教大家如何让我们的开发板进行DNS域名解…

AP5179 高端电流采样降压恒流驱动IC SOP8 LED车灯电源驱动

产品描述 AP5179是一款连续电感电流导通模式的降压恒流源&#xff0c;用于驱动一颗或多颗串联LED输入电压范围从 5 V 到 60V&#xff0c;输出电流 最大可达 2.0A 。根据不同的输入电压和外部器件&#xff0c; 可以驱动高达数十瓦的 LED。内置功率开关&#xff0c;采用高端电流…

MySQL性能优化

索引下推是什么&#xff1f; 索引下推是索引下推是 MySQL 5.6 及以上版本上推出的&#xff0c;用于对查询进行优化。 索引下推是把本应该在 server 层进行筛选的条件&#xff0c;下推到存储引擎层来进行筛选判断&#xff0c;这样能有效减少回表。 举例说明&#xff1a; 首先…

掌握Java JDK 1.8 API帮助文档中文版,事半功倍编程

文章目录 1. JDK 1.8 API帮助文档简介2. 如何查阅JDK 1.8 API帮助文档中文版2.1 在线文档2.2 本地文档2.3 集成开发环境&#xff08;IDE&#xff09; 3. 如何使用JDK 1.8 API帮助文档中文版3.1 寻找类和方法3.2 阅读文档说明3.3 查看示例代码 4. 总结 引言&#xff1a; Java是一…

Docker Compose 使用方法

目录 前言 安装 Docker Compose Ubuntu 安装与更新 Red Hat 安装与更新 验证是否安装 Docker Compose 创建 docker-compose.yml 文件 创建一个MySQL 与 tomcat 示例 使用Docker Compose启动服务 前言 Docker Compose 是一个工具&#xff0c;旨在帮助定义和 共享多容器…

Docker 容器生命周期:创建、启动、暂停与停止----从创建到停止多角度分析

&#x1f337;&#x1f341; 博主 libin9iOak带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——libin9iOak的博客&#x1f390; &#x1f433; 《面试题大全》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33…

解决Hadoop审计日志hdfs-audit.log过大的问题

【背景】 新搭建的Hadoop环境没怎么用&#xff0c;就一个环境天天空跑&#xff0c;结果今天运维告诉我说有一台服务器磁盘超过80%了&#xff0c;真是太奇怪了&#xff0c;平台上就跑了几个spark测试程序&#xff0c;哪来的数据呢&#xff1f; 【问题调查】 既然是磁盘写满了&…

Python案例分析|使用Python图像处理库Pillow处理图像文件

本案例通过使用Python图像处理库Pillow&#xff0c;帮助大家进一步了解Python的基本概念&#xff1a;模块、对象、方法和函数的使用 使用Python语言解决实际问题时&#xff0c;往往需要使用由第三方开发的开源Python软件库。 本案例使用图像处理库Pillow中的模块、对象来处理…

从互联网到云时代,Apache RocketMQ 是如何演进的?

作者&#xff1a;隆基 2022 年&#xff0c;RocketMQ 5.0 的正式版发布。相对于 4.0 版本而言&#xff0c;架构走向云原生化&#xff0c;并且覆盖了更多业务场景。 消息队列演进史 操作系统、数据库、中间件是基础软件的三驾马车&#xff0c;而消息队列属于最经典的中间件之一…

八大排序算法--希尔排序(动图理解)

目录 希尔排序 概念 算法思路 动画演示 代码如下 复杂度分析 时间复杂度测试 运行结果 完整代码 创作不易&#xff0c;如果本篇博客对您有一定的帮助&#xff0c;大家记得留言点赞哦。 希尔排序 概念 希尔排序是插入排序的一种&#xff0c;是对直接插入排序的优化。其…

华为数通HCIP-IP组播基础

点到点业务&#xff1a;比如FTP&#xff0c;WEB业务&#xff0c;此类业务主要特点是不同的用户有不同的需求&#xff0c;比如用户A需要下载资料A&#xff0c;用户B需要下载资料B。此类业务一般由单播承载&#xff0c;服务器对于不同用户发送不同的点到点数据流。 ospf、isis…

TP DP PP 并行训练方法介绍

这里写目录标题 张量并行TP流水线并行 PPnaive模型并行GPipePipeDream 数据并行DPFSDP 张量并行TP 挖坑 流水线并行 PP 经典的流水线并行范式有Google推出的Gpipe&#xff0c;和微软推出的PipeDream。两者的推出时间都在2019年左右&#xff0c;大体设计框架一致。主要差别为…

【Apollo学习笔记】—— Cyber RT之调度

文章目录 前言相关代码整理 调度介绍Cyber RT的改进实时操作系统资源限制&优先级协程 Cyber RT调度策略任务窃取两种任务类型componen组件自定义任务 Cyber调度实践配置文件DAG文件cyber_launch文件component组件BUILD文件 问题参考 前言 本文是对Cyber RT的学习记录,文章可…

devops(前端)

1.前言 前端的打包流程和后端的流程是一样的&#xff0c;只是打包的环境和制作的镜像有所不同&#xff0c;前端需要使用nodejs环境打包&#xff0c;镜像也是使用nginx镜像&#xff0c;因为用的是k8s的pod运行镜像&#xff0c;还需要使用configmap挂载nginx的配置&#xff0c;一…