题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
环城旅行

题目题干

背景

经过若干年的努力,Matrix67终于追到了自己喜爱的MM。他计划带她去一次环城旅行。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

描述

Matrix67要带他的女友进行一次环城旅行。他选择了一条总长度为L的封闭路线。他所选择的路线上有n个景点。他将从某个景点出发,顺时针开车绕城市一周,再回到出发点。出发前,油箱为空。每个景点内都有一个加油站,第i个景点的加油站提供的油可供车行驶Si的路程。所有加油站可提供的油的总和恰好够汽车行驶一周(即S1+S2+…+Sn=L)。汽车的油箱总能够容下所得到的汽油。临行前的那一天,Matrix67突然意识到,虽然所有加油站的油的总和等于汽车环城一周要消耗的油,但汽车不一定能环城一周,因为有可能还没有到下一个景点,汽油就用光了。显然,是否会发生半路上没油的情况取决于Matrix67选择的出发点。他可不希望和MM的这次浪漫的旅行就这样泡汤了。他知道每个景点离它前一个景点有多远,也知道每个景点的加油站提供的油量。他希望你能帮助他找出,从哪些景点出发可以顺利绕城一周。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

格式

输入格式

第一行为两个正整数,分别代表n和L。输入数据保证n<=500 000,L<=100 000 000,并且n<=L。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第二行到第n+1行这n行数据将按环行道路上顺时针的顺序依次描述各个景点。每行有两个正整数。第i+1行为Di和Si,分别表示第i个景点离其前一个景点(即第i-1个景点)的距离和这个景点的加油站所提供的油可供汽车行驶的距离。其中,D1=0。最后一个(第n个)景点与第一个景点之间的距离没有直接给出,但可以根据输入数据计算出来。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入数据保证,所有的Si之和等于L,所有的Di之和小于L。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式

一行正整数。输出时,每两个正整数之间都有一个空格,行末无空格。它们表示所有能够作为出发点顺利完成环城旅行的景点。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当存在多个这样的景点时,请按照升序排列输出他们的序号。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

当不存在这样的景点时,输出-1。6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例1

样例输入1

5 10
0 1
2 2
3 2
2 2
2 3

样例输出1

3 4 5

限制

各个测试点1s6Hk100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

答案解析

相关题目

连续数之和描述 有n个正整数排成一行。你的目的是要从中取出一个或连续的若干个数,使它们的和能够被k整除。 例如,有6个正整数,它们依次为1、2、6、3、7、4。若k=3,则你可以取出1、2、6,或者
环城旅行背景 经过若干年的努力,Matrix67终于追到了自己喜爱的MM。他计划带她去一次环城旅行。 描述 Matrix67要带他的女友进行一次环城旅行。他选择了一条总长度为L的封闭路线。他所选择的
野生动物园描述 cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内,这个区域从南到北被划分成N个区域,每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮
计算 (a+b)×c 的值题目描述 给定 3 个整数 a,b,c,计算表达式 (a+b)×c 的值。 输入格式 输入仅一行,包括三个整数 a,b,c,数与数之间以一个空格分开。 输出格式 输出一行
计算 (a+b)/c 的值题目描述 给定 3 个整数 a,b,c,计算表达式 (a+b)/c 的值,/ 是整除运算。 输入格式 输入仅一行,包括三个整数 a,b,c,数与数之间以一个空格分开。 输
带余除法题目描述 给定被除数和除数,求整数商及余数。此题中请使用默认的整除和取余运算,无需对结果进行任何特殊处理。 输入格式 一行,包含两个整数,依次为被除数和除数(除数非零),中间用一个空格隔开。
奇数求和
点亮灯笼题目描述 有 n 个灯笼环形摆放。最开始,这些灯笼都是关闭的状态。 操作台上有 n 个按钮,按下第 x 个按钮时,会反转灯笼 x 以及相邻两个灯笼的状态。「反转」是指关闭变成点亮、点亮变成关
计算分数加减表达式的值问题描述 编写程序,输入 n 的值,求 1/1−1/2+1/3−1/4+1/5−1/6+1/7−1/8+… 前 n 项的和。 输入格式 输入一个正整数 n ( 1≤n≤1000
将n拆成2个数的和

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢