【题解】JZOJ6645 / 洛谷P4090 [USACO17DEC] Greedy Gift Takers P
洛谷 P4090 [USACO17DEC] Greedy Gift Takers P
题意
n n n 头牛排成一列,队头的奶牛 i i i 拿一个礼物并插到从后往前数 c i c_i ci 头牛的前面,重复无限次,问多少奶牛没有礼物。
题解
发现若一头牛无法获得礼物,那么它后面的牛都无法获得礼物。
发现获得礼物的牛构成一个循环。
二分获得礼物的牛的数量。假设有 x x x 头牛获得礼物,仅考虑第 x x x 头牛能否获得礼物。让它获得礼物,就要把它推到前面去。假设前 x − 1 x-1 x−1 头牛都能获得礼物。于是把前 x − 1 x-1 x−1 头牛按 a a a 从小到大排序,也就是把牛尽可能往后插。
假设牛 x x x 后面有 l i m lim lim 头牛。若 x x x 前面的牛 i i i 满足 a i > l i m a_i>lim ai>lim,那么这个 x x x 无法获得礼物。因为 i i i 会插入到 x x x 的前面,又因为 a a a 值从小到大,那么 i i i 后面的牛都会插到 x x x 前面。若 a i ≤ l i m a_i\le lim ai≤lim, x x x 后面的牛多一头, l i m lim lim 加 1 1 1。
代码
#include <bits/stdc++.h>
using namespace std;
template<typename Ty> void read(Ty &x) {int c = getchar(), f = 1;for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);x *= f;
}
const int N = 100005;
int n, a[N], b[N], ans = 0;
bool check(int x) {for (int i = 1; i < x; i++) b[i] = a[i];sort(b + 1, b + x);int lim = n - x;for (int i = 1; i < x; i++, lim++)if (b[i] > lim)return 0;return 1;
}
int main() {read(n);for (int i = 1; i <= n; i++) read(a[i]);int l = 0, r = n;while (l <= r) {int mid = l + r >> 1;if (check(mid)) l = mid + 1, ans = mid;else r = mid - 1;}printf("%d", n - ans);return 0;
}
相关文章:
【题解】JZOJ6645 / 洛谷P4090 [USACO17DEC] Greedy Gift Takers P
洛谷 P4090 [USACO17DEC] Greedy Gift Takers P 题意 n n n 头牛排成一列,队头的奶牛 i i i 拿一个礼物并插到从后往前数 c i c_i ci 头牛的前面,重复无限次,问多少奶牛没有礼物。 题解 发现若一头牛无法获得礼物,那么它后…...
Vue 项目中的错误如何处理的?
1、 组件中的处理:使用 errorCaptured 钩子 作用:可以捕获来自后代组件的错误 父组件(errorCaptured) -> 子组件 (errorCaptured) -> 当孙子组件出错时,错误会一直向上抛,也就是先触发子组件的 errorCaptured,…...
网络分层的真实含义
复杂的程序都要分层,这是程序设计的要求。比如,复杂的电商还会分数据库层、缓存层、Compose 层、Controller 层和接入层,每一层专注做本层的事情。 当一个网络包从一个网口经过的时候,你看到了,首先先看看要不要请进来…...
RT-Thread 线程间同步
线程间同步 在多线程实时系统中,一项工作的完成往往可以通过多个线程协调的方式共同来完成,那么多个线程之间如何 “默契” 协作才能使这项工作无差错执行?下面举个例子说明。 例如一项工作中的两个线程:一个线程从传感器中接收…...
Python元类再解释
Python元类再解释 元类是什么? 你可以把元类看作是“生产类的工厂”。就像类是用来生产对象的,元类是用来生产类的。 为什么需要元类? 考虑一个场景:假设你正在编写一个框架,你希望框架中的所有类都有某些特定的方…...
常用的Spring Boot 注解及示例代码
简介:Spring Boot 是一个用于快速构建基于 Spring 框架的应用程序的工具,通过提供一系列的注解,它使得开发者可以更加轻松地配置、管理和控制应用程序的各种行为。以下是一些常用的 Spring Boot 注解,以及它们的功能和示例代码&am…...
react app教程
react app教程 环境准备 下载node 下载npx npm install npx创建app npx create-react-app automedia cd automedia npm start构建发布版本 npm run build安装调试工具 # .vscode/launch.json {// 使用 IntelliSense 了解相关属性。 // 悬停以查看现有属性的描述。// 欲了…...
在vue项目中用vue-watermark快捷开发屏幕水印效果
我们先引入一个第三方依赖 npm install vue-watermark然后 因为这只是个测试工具 我就直接代码写 App.vue里啦 参考代码如下 <template><div><vue-watermark :text"watermarkText"></vue-watermark><!-- 正常的页面内容 --></div…...
无涯教程-Android - Activity
Activity代表具有用户界面的单个屏幕,就像Java的窗口或框架一样。Android Activity 是ContextThemeWrapper类的子类。 如果您使用过C,C或Java编程语言,那么您一定已经看到您的程序从 main()函数开始。与之非常相似,Android系统以 …...
vue项目前端展示数学公式(在表格中渲染)
现有需求为 将实验数据录入表格中,需要表格呈现物理公式,使用Mathjax在vue2中 进行呈现 1.安装 npm i --save mathjax-vue 2.全局注册(main.js中) import MathJax, { initMathJax, renderByMathjax } from mathjax-vuefunction onMathJaxReady() {const el document.getEl…...
java八股文面试[数据库]——MySQL索引的数据结构
知识点: 【2023年面试】mysql索引的基本原理_哔哩哔哩_bilibili 【2023年面试】mysql索引结构有哪些,各自的优劣是什么_哔哩哔哩_bilibili...
python3.11教程2:基础数据类型(数字和字符串)、组合数据类型(集合、元组、列表、字典)
文章目录 五、基本数据类型5.1 整数和浮点数5.1.1 整数和浮点数的类型5.1.2 进制和进制转换5.1.3 round函数 5.2 运算符5.2.1 常用运算符、运算符函数和逻辑运算符5.2.2 位运算符5.2.3 运算符的优先级及其进阶使用 5.3 布尔类型5.4 字符串5.3.1 字符串的基本操作5.3.2 字符串函…...
剑指 Offer 44. 数字序列中某一位的数字(中等)
题目: class Solution { //本题单纯找规律,要注意通过n%digits来判断有几个位数为digits的数 public:int findNthDigit(int n) {long base 9, digits 1; //digits代表位数while(n-base*digits>0){ //该循环是为了确定目标数字所在…...
SpringBoot中HttpClient的学习
一、介绍 HttpClient是Apache Jakarta Common 下的子项目,可以用来提供高效的、最新的、功能丰富的支持 HTTP 协议的客户端编程工具包。 HttpClient 是一个HTTP通信库、一个工具包,它只提供一个通用浏览器应用程序所期望的功能子集,与浏览…...
JVM-内存溢出的原因、CPU占满的原因
1.内存溢出的原因 OOM的排查思路_oom排查_java排坑日记的博客-CSDN博客 每个进程的内存(限制,譬如2G)最大堆容量最大方法区容量程序计数器虚拟机栈和本地方法栈。多线程下每个线程栈越大,越容易OOM. 1.堆内存溢出(OO…...
如何做好银行统一报送系统UI设计
北京蓝蓝设计公司是一支由清华美院毕业的专业团队组成的设计公司。我们的设计师们在金融银行软件领域拥有12年的工作经验和丰富的行业知识。 在工作中我们常常思考银行金融反洗钱软件用户使用痛点是什么?我们发现用户的使用痛点往往是: 1功能入口不清晰…...
988. 从叶结点开始的最小字符串
988. 从叶结点开始的最小字符串 C代码:DFS /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/// 叶子节点// 每一层用一个pathTop、遇到叶子节点就判断一次;…...
RealSense D455启动教程
环境: ubuntu20.04 ros:noetic 视觉传感器:Intel RealSense D455 通过命令安装不成功后改为下面源码安装 1. 安装Intel RealSense SDK 2.0 1.1源码安装 1. 下载源码git clone https://github.com/IntelRealSense/librealsense cd librealsense…...
docker与phpstudy两种方式部署wordpress 并 开启伪静态
实际测试,可能是docker内存限制的缘故,docker部署的会比较卡 下载 wordpress phpstudy phpstudy中伪静态配置 伪静态 正常访问 WordPress 文章页的 URL 地址为 http://asa/index.php?p123。变成伪静态就是http://asa/123.html 。 伪静态是相对真实静…...
网站搭建最简化的引导操作 | 云服务器的购买选用 | 域名的选用 | 网站的上线和备案。
本文章面向对象为网站搭建的初次操作者,主要是一些自主使用的网站,为小白做为引导的教程。 一, 网站搭建的流程 1,服务器的租赁 2,购买域名 3,对域名进行备案 4,网站内部的搭建,上线…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
