数组已经非递减排好。四个答案都可以由两次二分得到,不必从左扫到右。
把数组想成两段分界:
# 题目内容
给定一个长度为 n 的非递减整数数组 a0,a1,…,an−1(已排好序,允许重复),以及一个整数 T。数组下标从 0 开始。
请输出四个整数,依次表示:
第一行两个整数 n、T。
第二行 n 个整数 a0,a1,…,an−1,保证 a0≤a1≤⋯≤an−1。
1≤n≤105
−109≤ai,T≤109
输出一行四个整数,分别对应上述四个答案,相邻整数之间用一个空格分隔。
输入
5 2
1 2 2 2 4
输出
1 3 0 4
说明
T=2 出现在下标 1,2,3。第一次出现是 1,最后一次出现是 3。小于 2 的最大下标是 0(值为 1),大于 2 的最小下标是 4(值为 4)。
输入
4 3
1 2 4 5
输出
-1 -1 1 2
说明
数组中没有 3,因此前两个答案为 −1。小于 3 的最大下标是 1(值为 2),大于 3 的最小下标是 2(值为 4)。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册