当前位置: 首页 > news >正文

【题解】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 x1 头牛都能获得礼物。于是把前 x − 1 x-1 x1 头牛按 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 ailim 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 头牛排成一列&#xff0c;队头的奶牛 i i i 拿一个礼物并插到从后往前数 c i c_i ci​ 头牛的前面&#xff0c;重复无限次&#xff0c;问多少奶牛没有礼物。 题解 发现若一头牛无法获得礼物&#xff0c;那么它后…...

Vue 项目中的错误如何处理的?

1、 组件中的处理&#xff1a;使用 errorCaptured 钩子 作用&#xff1a;可以捕获来自后代组件的错误 父组件(errorCaptured) -> 子组件 (errorCaptured) -> 当孙子组件出错时&#xff0c;错误会一直向上抛&#xff0c;也就是先触发子组件的 errorCaptured&#xff0c;…...

网络分层的真实含义

复杂的程序都要分层&#xff0c;这是程序设计的要求。比如&#xff0c;复杂的电商还会分数据库层、缓存层、Compose 层、Controller 层和接入层&#xff0c;每一层专注做本层的事情。 当一个网络包从一个网口经过的时候&#xff0c;你看到了&#xff0c;首先先看看要不要请进来…...

RT-Thread 线程间同步

线程间同步 在多线程实时系统中&#xff0c;一项工作的完成往往可以通过多个线程协调的方式共同来完成&#xff0c;那么多个线程之间如何 “默契” 协作才能使这项工作无差错执行&#xff1f;下面举个例子说明。 例如一项工作中的两个线程&#xff1a;一个线程从传感器中接收…...

Python元类再解释

Python元类再解释 元类是什么&#xff1f; 你可以把元类看作是“生产类的工厂”。就像类是用来生产对象的&#xff0c;元类是用来生产类的。 为什么需要元类&#xff1f; 考虑一个场景&#xff1a;假设你正在编写一个框架&#xff0c;你希望框架中的所有类都有某些特定的方…...

常用的Spring Boot 注解及示例代码

简介&#xff1a;Spring Boot 是一个用于快速构建基于 Spring 框架的应用程序的工具&#xff0c;通过提供一系列的注解&#xff0c;它使得开发者可以更加轻松地配置、管理和控制应用程序的各种行为。以下是一些常用的 Spring Boot 注解&#xff0c;以及它们的功能和示例代码&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代表具有用户界面的单个屏幕&#xff0c;就像Java的窗口或框架一样。Android Activity 是ContextThemeWrapper类的子类。 如果您使用过C&#xff0c;C或Java编程语言&#xff0c;那么您一定已经看到您的程序从 main()函数开始。与之非常相似&#xff0c;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索引的数据结构

知识点&#xff1a; 【2023年面试】mysql索引的基本原理_哔哩哔哩_bilibili 【2023年面试】mysql索引结构有哪些&#xff0c;各自的优劣是什么_哔哩哔哩_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. 数字序列中某一位的数字(中等)

题目&#xff1a; class Solution { //本题单纯找规律&#xff0c;要注意通过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 下的子项目&#xff0c;可以用来提供高效的、最新的、功能丰富的支持 HTTP 协议的客户端编程工具包。 HttpClient 是一个HTTP通信库、一个工具包&#xff0c;它只提供一个通用浏览器应用程序所期望的功能子集&#xff0c;与浏览…...

JVM-内存溢出的原因、CPU占满的原因

1.内存溢出的原因 OOM的排查思路_oom排查_java排坑日记的博客-CSDN博客 每个进程的内存&#xff08;限制&#xff0c;譬如2G&#xff09;最大堆容量最大方法区容量程序计数器虚拟机栈和本地方法栈。多线程下每个线程栈越大&#xff0c;越容易OOM. 1.堆内存溢出&#xff08;OO…...

如何做好银行统一报送系统UI设计

北京蓝蓝设计公司是一支由清华美院毕业的专业团队组成的设计公司。我们的设计师们在金融银行软件领域拥有12年的工作经验和丰富的行业知识。 在工作中我们常常思考银行金融反洗钱软件用户使用痛点是什么&#xff1f;我们发现用户的使用痛点往往是&#xff1a; 1功能入口不清晰…...

988. 从叶结点开始的最小字符串

988. 从叶结点开始的最小字符串 C代码&#xff1a;DFS /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/// 叶子节点// 每一层用一个pathTop、遇到叶子节点就判断一次&#xff1b;…...

RealSense D455启动教程

环境&#xff1a; ubuntu20.04 ros:noetic 视觉传感器&#xff1a;Intel RealSense D455 通过命令安装不成功后改为下面源码安装 1. 安装Intel RealSense SDK 2.0 1.1源码安装 1. 下载源码git clone https://github.com/IntelRealSense/librealsense cd librealsense…...

docker与phpstudy两种方式部署wordpress 并 开启伪静态

实际测试&#xff0c;可能是docker内存限制的缘故&#xff0c;docker部署的会比较卡 下载 wordpress phpstudy phpstudy中伪静态配置 伪静态 正常访问 WordPress 文章页的 URL 地址为 http://asa/index.php?p123。变成伪静态就是http://asa/123.html 。 伪静态是相对真实静…...

网站搭建最简化的引导操作 | 云服务器的购买选用 | 域名的选用 | 网站的上线和备案。

本文章面向对象为网站搭建的初次操作者&#xff0c;主要是一些自主使用的网站&#xff0c;为小白做为引导的教程。 一&#xff0c; 网站搭建的流程 1&#xff0c;服务器的租赁 2&#xff0c;购买域名 3&#xff0c;对域名进行备案 4&#xff0c;网站内部的搭建&#xff0c;上线…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...