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

P3957 [NOIP2017 普及组] 跳房子

题目背景

NOIP2017 普及组 T4

题目描述

跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下:

在地面上确定一个起点,然后在起点右侧画 nn 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 dd。小 R 希望改进他的机器人,如果他花 gg 个金币改进他的机器人,那么他的机器人灵活性就能增加 gg,但是需要注意的是,每 次弹跳的距离至少为 11。具体而言,当 g<dg<d 时,他的机器人每次可以选择向右弹跳的距离为 d-g,d-g+1,d-g+2,\ldots,d+g-1,d+gd−g,d−g+1,d−g+2,…,d+g−1,d+g;否则当 g \geq dg≥d 时,他的机器人每次可以选择向右弹跳的距离为 1,2,3,\ldots,d+g-1,d+g1,2,3,…,d+g−1,d+g。

现在小 R 希望获得至少 kk 分,请问他至少要花多少金币来改造他的机器人。

输入格式

第一行三个正整数 n,d,kn,d,k ,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 nn 行,每行两个整数 x_i,s_ixi​,si​ ,分别表示起点到第 ii 个格子的距离以及第 ii 个格子的分数。两个数之间用一个空格隔开。保证 x_ixi​ 按递增顺序输入。

输出格式

共一行,一个整数,表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 kk 分,输出 -1−1。

输入输出样例

输入 #1复制

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出 #1复制

2

输入 #2复制

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

输出 #2复制

-1

说明/提示

输入输出样例 1 说明

花费 22 个金币改进后,小 R 的机器人依次选择的向右弹跳的距离分别为 2, 3, 5, 3, 4,32,3,5,3,4,3,先后到达的位置分别为 2, 5, 10, 13, 17, 202,5,10,13,17,20,对应1, 2, 3, 5, 6, 71,2,3,5,6,7 这 66 个格子。这些格子中的数字之和 1515 即为小 R 获得的分数。

输入输出样例 2 说明

由于样例中 77 个格子组合的最大可能数字之和只有 1818,所以无论如何都无法获得 2020 分。

数据规模与约定

本题共 10 组测试数据,每组数据等分。

对于全部的数据满足1 \le n \le 5\times10^51≤n≤5×105,1 \le d \le2\times10^31≤d≤2×103,1 \le x_i, k \le 10^91≤xi​,k≤109,|s_i| < 10^5∣si​∣<105。

对于第 1, 21,2 组测试数据,保证 n\le 10n≤10。

对于第 3, 4, 53,4,5 组测试数据,保证 n \le 500n≤500。

对于第 6, 7, 86,7,8 组测试数据,保证 d = 1d=1。

 

/*
Problem : luogu P3957
Algorithm : 二分 + 单调队列dp 
Status : 
*/
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#define int long long
using namespace std;
typedef long long ll;const int INF = 0x3f3f3f3f3f;
const int MAXN = 1000005;int n,d,k;
int f[MAXN],x[MAXN],s[MAXN];
deque<int> q;bool check(int mi,int mx){memset(f,0,sizeof(f));int p = 0;while(!q.empty())q.pop_back();for(int i = 1;i <= n;i++){while(x[i] >= x[p] + mi){while(!q.empty() && f[p] > f[q.back()])q.pop_back();q.push_back(p);p++;}while(!q.empty() && x[i] > x[q.front()] + mx)q.pop_front();if(q.empty())f[i] = -INF;elsef[i] = f[q.front()] + s[i];if(f[i] >= k)return true;}return false;
}signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);scanf("%lld%lld%lld",&n,&d,&k);for(int i = 1;i <= n;i++)scanf("%lld%lld",&x[i],&s[i]);int l = 0,r = INF,ans = -1;while(l <= r){int mid = (r - l) / 2 + l;if(check(max(1ll,d - mid),d + mid)){r = mid - 1;ans = mid;}elsel = mid + 1;}printf("%lld\n",ans);return 0;
}

相关文章:

P3957 [NOIP2017 普及组] 跳房子

题目背景 NOIP2017 普及组 T4 题目描述 跳房子&#xff0c;也叫跳飞机&#xff0c;是一种世界性的儿童游戏&#xff0c;也是中国民间传统的体育游戏之一。 跳房子的游戏规则如下&#xff1a; 在地面上确定一个起点&#xff0c;然后在起点右侧画 nn 个格子&#xff0c;这些…...

VR数字工厂多元化展现,打造数字企业工厂名片

5G时代&#xff0c;各种营销都在走数字化的路子&#xff0c;VR数字工厂用VR赋能工厂数字升级&#xff0c;将企业环境、工厂生产、产品研发、质检运输等流程&#xff0c;无死角720度的展示在客户面前&#xff0c;不仅可以提升自身企业的实力&#xff0c;还可以提高客户的信任感。…...

uniapp封装组件,选中后右上角显示对号√样式(通过css实现)

效果&#xff1a; 一、组件封装 1、在项目根目录下创建components文件夹&#xff0c;自定义组件名称&#xff0c;我定义的是xc-button 2、封装组件代码 <template><view class"handle-btn"><view :class"handleIdCode 1 ? select : unSelec…...

华为OD面试(部分)

笔试与性格测验 一面 问题和算法题都挺简单的 二面 Java内存泄漏 算法题思路不对&#xff0c;没写完只说了下思路&#xff1a;Leetcode516. Longest Palindromic Subsequence hr面&#xff08;资面&#xff09; 最后告诉我hr面挂了。其实这不是最重要的&#xff0c;因为还…...

从零做软件开发项目系列之一综论软件项目开发

1 引言 有一个三个泥瓦匠的故事。 三个泥瓦匠在砌墙&#xff0c;一个人走过来&#xff0c;问他们在干什么。   第一个泥瓦匠没好气地说&#xff0c;你没看见吗&#xff1f;我在辛苦地砌墙呢。   第二个回答&#xff0c;我们正在建一座高楼。   第三个则洋溢着喜悦说&…...

msvcp110.dll是什么意思,msvcp110.dll丢失的解决方法

装好软件或游戏之后&#xff0c;一打开就跳出各种报错信息的情况小伙伴一定见过&#xff0c;其中缺少各种msvcp110.dll文件最常见。小伙伴们一定奇怪&#xff0c;用得好好的电脑&#xff0c;怎么会缺文件呢&#xff1f;为啥其他游戏/应用就没事呢&#xff1f;其实这些“丢失”的…...

【报错】git push --set-upstream origin XXXX重名

您在尝试将分支推送到远程仓库时遇到了错误。错误信息表明&#xff0c;由于已经存在名为 refs/heads/xingfan/demo 的文件夹&#xff0c;Git 无法创建分支 refs/heads/xingfan。 要解决此问题&#xff0c;您可以尝试重命名本地分支&#xff0c;然后将其推送到远程仓库。以下是…...

探索树算法:C语言实现二叉树与平衡树

探索树算法&#xff1a;C语言实现二叉树与平衡树 树是计算机科学中一个重要且广泛应用的数据结构&#xff0c;它在许多领域都有着重要作用。本篇博客将深入介绍两种常见的树算法&#xff1a;二叉树遍历和平衡二叉树&#xff08;AVL树&#xff09;&#xff0c;并提供在C语言中的…...

Ubuntu 20.04(服务器版)安装 Anaconda

0、Anaconda介绍 Anaconda是一个开源的Python发行版本&#xff0c;包含了包括Python、Conda、科学计算库等180多个科学包及其依赖项。因此&#xff0c;安装了Anaconda就不用再单独安装CUDA、Python等。 CUDA&#xff0c;在进行深度学习的时候&#xff0c;需要用到GPU&#xf…...

IDEA项目实践——JavaWeb简介以及Servlet编程实战

系列文章目录 IDEA项目实践——创建Java项目以及创建Maven项目案例、使用数据库连接池创建项目简介 IDEWA项目实践——mybatis的一些基本原理以及案例 IDEA项目实践——动态SQL、关系映射、注解开发 IDEA项目实践——Spring框架简介,以及IOC注解 IDEA项目实践——Spring当…...

【Freertos基础入门】队列(queue)的使用

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、队列是什么&#xff1f;二、队列的操作二、示例代码总结 前言 本系列基于stm32系列单片机来使用freerots FreeRTOS是一个广泛使用的开源实时操作系统&…...

从零构建深度学习推理框架-8 卷积算子实现

其实这一次课还蛮好理解的&#xff1a; 首先将kernel展平&#xff1a; for (uint32_t g 0; g < groups; g) {std::vector<arma::fmat> kernel_matrix_arr(kernel_count_group);arma::fmat kernel_matrix_c(1, row_len * input_c_group);for (uint32_t k 0; k < k…...

【Spring Boot】JdbcTemplate数据连接模板 — JdbcTemplate入门

JdbcTemplate入门 本节从基础的部分开始介绍什么是JDBC、什么是JdbcTemplate&#xff0c;然后介绍Spring Boot项目如何使用JdbcTemplate操作数据库。 1.JdbcTemplate简介 1.1 什么是JDBC JDBC&#xff08;Java Data Base Connectivity&#xff0c;Java数据库连接&#xff0…...

视频汇聚集中存储EasyCVR平台调用iframe地址视频无法播放,该如何解决?

安防监控视频汇聚平台EasyCVR基于云边端一体化架构&#xff0c;具有强大的数据接入、处理及分发能力&#xff0c;可提供视频监控直播、云端录像、视频云存储、视频集中存储、视频存储磁盘阵列、录像检索与回看、智能告警、平台级联、云台控制、语音对讲、AI算法中台智能分析无缝…...

从今天起,重新出发

2017年的时候&#xff0c;我还是一名在校大学生&#xff0c;当时为了准备实习面试写下了第一篇学习笔记。 2018年我开始工作&#xff0c;简单记录了使用 Airflow 的踩坑记录。 一直到今天我已经是一个工作了五年的社畜&#xff0c;但是很遗憾没有把工作中的成长记录下来。 当…...

Java多态详解(1)

多态 多态的概念 所谓多态&#xff0c;通俗地讲&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。 比如&#xff1a; 这一时间爆火的“现代纪录片”中&#xff0c;麦克阿瑟总是对各种“名人”有不同的评价&…...

optee读取Arm系统寄存器的模板

先写一个通用的内联函数模板,然后再通过宏控来定义各种读写函数。 (core/arch/arm/include/arm64.h)/** Templates for register read/write functions based on mrs/msr*/#define DEFINE_REG_READ_FUNC_(reg, type, asmreg) \ sta...

VSCode 使用总结

快捷键 在 Visual Studio Code (VSCode) 中&#xff0c;有许多常用的快捷键可以提高编程效率。以下是一些常见的 VSCode 编程项目快捷键&#xff1a; 编辑器操作&#xff1a; 撤销&#xff1a;Ctrl Z重做&#xff1a;Ctrl Shift Z复制&#xff1a;Ctrl C剪切&#xff1a;C…...

GuLi商城-前端基础Vue-使用Vue脚手架进行模块化开发

自己亲自实践&#xff1a; mac安装webpack webpack 简介Webpack 是一个非常流行的前端构建工具&#xff0c;它可以将多个模块&#xff08;包括CSS、JavaScript、图片等&#xff09;打包成一个或多个静态资源文件&#xff08;bundle&#xff09;&#xff0c;以便用于部署到生产…...

LeetCode450. 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 文章目录 [450. 删除二叉搜索树中的节点](https://leetcode.cn/problems/delete-node-in-a-bst/)一、题目二、题解方法一&#xff1a;递归&#xff08;一种麻烦的方法&#xff09;方法二&#xff1a;优化后的递归 一、题目 给定一个二叉搜索树的根…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...