灵台门户网站建设,怎么向搜索引擎提交网站,简单wordpress主题,wordpress中文tag插件题目描述 给定一个按照升序排列的长度为n的整数数组#xff0c;以及 q 个查询。 对于每个查询#xff0c;返回一个元素k的起始位置和终止位置#xff08;位置从0开始计数#xff09;。 如果数组中不存在该元素#xff0c;则返回“-1 -1”。 输入格式 第一行包含整数n和q以及 q 个查询。 对于每个查询返回一个元素k的起始位置和终止位置位置从0开始计数。 如果数组中不存在该元素则返回“-1 -1”。 输入格式 第一行包含整数n和q表示数组长度和询问个数。 第二行包含n个整数均在1~10000范围内表示完整数组。 接下来q行每行包含一个整数k表示一个询问元素。 输出格式 共q行每行包含两个整数表示所求元素的起始位置和终止位置。 如果数组中不存在该元素则返回“-1 -1”。 数据范围 1≤n≤100000 1≤n≤100000 1≤q≤10000 1≤q≤10000 1≤k≤10000 1≤k≤10000 样例 输入样例
6 3
1 2 2 3 3 4
3
4
5
输出样例
3 4
5 5
-1 -1分析
用二分去查找元素要求数组拥有两段性即数组中的元素存在分界线给定条件可以将集合中元素分为两部分一部分满足条件一部分不满足条件。对本题而言一个包含重复元素的有序序列要求输出某元素出现的起始位置和终止位置翻译一下就是在数组中查找某元素找不到就输出−1−1的第一个位置较为简单
int l 0, r n - 1;
while (l r) {int mid l r 1;if (a[mid] x) l mid 1;else r mid;
}当a[mid]xa[mid]x的最后一个位置便不容易了
int l1 l, r1 n;
while (l1 1 r1) {int mid l1 r1 1;if (a[mid] x) l1 mid;else r1 mid;
}要查找不大于x的最后一个位置
当a[mid]xa[mid]x是开区间。上面这种写法修改了循环条件使得二分不会死循环修改了区间的开闭性使得不会查找错误。另一种解决办法就是
int l 0, r n - 1;
while (l r){int mid l r 1 1;if (a[mid] x) l mid;else r mid - 1;}不修改循环终止条件想办法解决死循环的问题首先想下为什么查找不小于xx.
是否还有其他办法既不修改区间的开闭性和循环终止条件又不用上取整呢答案是肯定的。
int l1 l, r1 n - 1;
while (l1 r1) {int mid l1 r1 1;if (a[mid] x) l1 mid 1;else r1 mid - 1;
}
printf(%d %d\n, l, l1 - (a[l1] x ? 0 : 1));我们之所以会进行第二轮查找不大于xx所以加上这个判断就可以解决该问题了。这也是二分程序可能遇见的第三种问题当左右指针都移动时待查找元素处在元素末尾会引起查找错误。总的代码如下
#include iostream
using namespace std;
const int maxn 100005;
int n, q, x, a[maxn];
int main() {scanf(%d%d, n, q);for (int i 0; i n; i) scanf(%d, a[i]);while (q--) {scanf(%d, x);int l 0, r n - 1;while (l r) {int mid l r 1;if (a[mid] x) l mid 1;else r mid;}if (a[l] ! x) {printf(-1 -1\n);continue;}int l1 l, r1 n;while (l1 1 r1) {int mid l1 r1 1;if (a[mid] x) l1 mid;else r1 mid;}printf(%d %d\n, l, l1);}return 0;
}
