AcWing 每日一题 2022/5/4【2031. 折叠绳子】

农夫约翰有一条长度为 L 的绳子,可用于农场周围的各种任务。 绳子在不同的位置有 N 个绳结&#…

农夫约翰有一条长度为 L 的绳子,可用于农场周围的各种任务。

绳子在不同的位置有 N 个绳结,包括两个端点处各有一个。

约翰注意到,在某些位置,他可以将绳子对折,这样,相对的绳索上的绳结就可以彼此完全对齐:

在这里插入图片描述

请帮助约翰统计具有此属性的折叠点数。

允许在某个绳结处折叠,但不允许在端点绳结处折叠。

折叠后,较长的一侧可以有多余节点。

输入格式
第一行包含两个整数 N 和 L。

接下来 N 行,每行包含一个 0∼L 范围内的数,表示一个绳结的位置。其中两行包含的数字分别是 0 和 L。

输出格式
输出有效折叠位置的数量。

数据范围

1≤L≤10000,
1≤N≤100

输入样例:

输出样例:

样例解释
有效折叠位置为 1,2,3,8。

题目分析

给定一段绳子,然后绳子上某些位置有绳结,然后判断有多少个位置折叠后,可以将绳结全部匹配(超出的部分可以不匹配,没有超出的部分一定要完全匹配)
难点:折叠的点可能不是整数,可能是一个小数,比如 0 和 1 的中点可以进行折叠,使得 0 和 1 匹配
处理方法:将全部的数据进行 *2 处理,将中点的情况全部规避掉
时间复杂度O(104)

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/2572.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部