【NOIP2017】跳房子

简介: 笔记

题目描述


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


在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。


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


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


输入描述:


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


接下来 n 行,每行两个正整数𝑥𝑖, 𝑠𝑖,分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证𝑥𝑖按递增顺序输入。


输出描述:


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

示例1


输入


7 4 10

2 6

5 -3

10 3

11 -3

13 1

17 6

20 2

输出


2

说明


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

示例2


输入


7 4 20

2 6

5 -3

10 3

11 -3

13 1

17 6

20 2

输出


-1

说明


由于样例中 7 个格子组合的最大可能数字之和只有 18 ,无论如何都无法获得 20 分


解答

不难想到二分g,判断一下,朴素的算法是n^2 ×log(n)的。

check()函数:

O(n^2)做法:

f[i]表示到第i个点的最大分数。

f[i]=max(f[j])+s[i](J满足x[j]+Max >= x[i],x[j]+Min <= x[i])

O(n)的做法:

单调队列优化,

1.用一个指针now记录入栈的结点,当Minx[i]−x[now]≥Min进入循环,

在循环的过程中去除无法到达的now,把合法的结点加入栈。

2.将满足上述条件的情况下,去除x[pos[l]]+Max<x[i]的情况,

如果l>r表示没有解。赋值为-INF,反之更新。


代码:


#include<bits/stdc++.h>
#define ll long long 
#define R register
using namespace std;
const int N=5e5+5;
int n,d,k,s[N],x[N],ans=0x3f3f3f3f,f[N];
int pos[N];
inline int check(R int g)//二分g
{
    //f[i] 表示 到第i个点 得到分数的最大值
    //f[i]=max(f[i],f[j]+s[i]);j满足   x[j]+Max>=x[i]
    //                            x[j]+Min<=x[i]
    memset(pos,0,sizeof(pos));
    memset(f,0,sizeof(f));
    R int Min=max(1,d-g);
    R int Max=d+g;
    R int l=1,r=0,now=0;
    if(Max<x[1])return 1;
    for(R int i=1;i<=n;i++)
    {
            while(x[i]-x[now]>=Min)
            {
                if(f[now]<=-0x3f3f3f3f)
                {
                    now++;
                    continue;
                }
                while(f[now]>=f[pos[r]]&&l<=r)r--;
                pos[++r]=now;
                now++;
            }
            while(x[pos[l]]+Max<x[i]&&l<=r)l++;
            if(l<=r)
            f[i]=f[pos[l]]+s[i];
            else
            f[i]=-0x3f3f3f3f;
            //printf("%d %d\n",i,f[i]);
            if(f[i]>=k)return 0;
    }
    return 1;
}
int main(){
    R int l=0,r=0;
    scanf("%d%d%d",&n,&d,&k);
    for(R int i=1;i<=n;i++)
    scanf("%d%d",&x[i],&s[i]);
    r=x[n];
    while(l<r)
    {
        R int mid=(l+r)/2;
        if(check(mid))
        {
            l=mid+1;
        }
        else
        {
            r=mid;
            ans=min(ans,mid);
        }
    }
    if(ans==0x3f3f3f3f)
    printf("-1");
    else
    printf("%d",ans);
    return 0;
}


相关文章
|
6天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
16天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1317 7
|
4天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
284 128
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
15天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1375 87
|
3天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。
|
4天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
259 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
|
5天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
217 82
2025年阿里云域名备案流程(新手图文详细流程)