首页 > 试题广场 >

万万没想到之抓捕孔连顺

[编程题]万万没想到之抓捕孔连顺
  • 热度指数:57441 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
我叫王大锤,是一名特工。我刚刚接到任务:在字节跳动大街进行埋伏,抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工,我提议

1. 我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
2. 为了相互照应,我们决定相距最远的两名特工间的距离不超过 D 。

我特喵是个天才! 经过精密的计算,我们从X种可行的埋伏方案中选择了一种。这个方案万无一失,颤抖吧,孔连顺!
……
万万没想到,计划还是失败了,孔连顺化妆成小龙女,混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了,就是杨过本人来了也发现不了的!

请听题:给定 N(可选作为埋伏点的建筑物数)、 D(相距最远的两名特工间的距离的最大值)以及可选建筑的坐标,计算在这次行动中,大锤的小队有多少种埋伏选择。
注意:
1. 两个特工不能埋伏在同一地点
2. 三个特工是等价的:即同样的位置组合( A , B , C ) 只算一种埋伏方法,不能因“特工之间互换位置”而重复使用


数据范围:

输入描述:
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N个建筑物的的位置,每个位置用一个整数(取值区间为[0, 1000000])表示,从小到大排列(将字节跳动大街看做一条数轴)


输出描述:
一个数字,表示不同埋伏方案的数量。结果可能溢出,请对 99997867 取模
示例1

输入

4 3
1 2 3 4

输出

4

说明

可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)   
示例2

输入

5 19
1 10 20 30 50

输出

1

说明

可选方案 (1, 10, 20)   
示例3

输入

2 100
1 102

输出

0

说明

无可选方案  
头像 生命不息手撕不止
发表于 2019-08-10 16:50:34
主要思路就是每读取一个数字,就判断窗口是否满足最大值减去最小值不大于距离D;由于每次进行计算组合之后,窗口的begin都会往前移动一位,所以计算组合应该采用固定首位的方法,即固定首位有一人,接下来的位置的可能性,这样就可以保证窗口移动过程不会出现重复,因为下一次判断已经不包含上一个的首位置了。 #i 展开全文
头像 遍地狼烟
发表于 2021-09-20 22:22:43
主要变量:first(当arr[last]-arr[first]>D时,循环加1,直到小于D或first=last结束),last(一直加一输入)。主要思路:首先不能位置重复,只需要根据输入的last++位置往前寻找即可,因为每次的last都不一样,所以位置一定不会一样,每次last+1都通过 展开全文
头像 猫咚
发表于 2020-11-05 21:28:22
字节跳动面试题 —— 万万没想到之聪明的编辑 题目 我叫王大锤,是一家出版社的编辑。我负责校对投稿来的英文稿件,这份工作非常烦人,因为每天都要去修正无数的拼写错误。但是,优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径: 三个同样的字母连在一起,一定是拼写错误,去掉一个的就好啦:比 展开全文
头像 bitmap
发表于 2022-02-28 23:00:34
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); 展开全文
头像 Hilory
发表于 2021-10-09 10:37:09
血的教训,在计算中间结果的时候也要用long long保存,不然结果会溢出!!! 附上C++二分查找代码 #include <iostream> #include <vector> using namespace&n 展开全文
头像 ZX2021
发表于 2021-07-30 16:28:38
读入整数到vector中,每次都固定最左边的位置,然后查找满足最条件的最右边的位置,中间的位置个数可进行排列组合,假如有nums个,则这种情况的解有nums*(nums-1)/2种情况。然后将最左边的位置向右移动一个继续统计,最右边的位置在满足条件的情况下需要进行更新,不需要从最左边的位置重新开始计 展开全文
头像 夜来ZKH
发表于 2022-06-24 12:54:27
题目的要求是相距最远的2个人距离不超过d,所以当我们确定了距离最远的2个人的距离,那么第3个人的坐标就是在这2人之间进行排列组合。所以问题就转化为给定一有序数组a,对于a中的每一个元素查找出距离最大且小于d的另一个元素 普通直接遍历会超时因为数组有序,可以用二分查找或者滑动窗口(记得开long lo 展开全文
头像 hhhhh1234
发表于 2022-08-15 10:33:11
代码思路: 双指针 + 组合数 定义j指针,遍历a[j] - a[i] <= d,就是当前第一个在i位置得到最远能到的j位置,再从i + 1 到 j中选两个位置 //双指针算法 #include<iostream> using namespace s 展开全文
头像 青春猪头少年不会没有offer
发表于 2023-12-21 09:30:58
解法1——二分查找 用二分查找寻找以l为开头时,可行的最后一个r。 那么[l,r]区间的方案数为1+2+...+(r-l-1)。 import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { 展开全文
头像 Bob爱学习
发表于 2022-03-16 21:11:30
public class Main{ public static int mod = 99997867; public static void main(String[] args){ long count = 0; Scanner sc = new 展开全文