寒假集训5——二分
这三题我都超时了，优化完可能会再上传。这些都不是AC代码，请批判性查阅，轻喷！！！
1.B2166 查找不重复元素出现的位置
题目描述
输入 n 个不超过 109 的严格递增的正整数组成的数列 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中出现的下标。如果序列中不包含该数字，请输出 −1 。
注意：下标从 1 开始。
输入格式
第一行，包含两个正整数 n 和 m，分别表示数列的长度和询问的次数。
第二行，包含 n 个正整数 a1,a2,…,an。
接下来 m 行，每行包含一个正整数 q，表示一次询问。
输出格式
输出共 m 行。
对于每次询问，如果数字 q 存在于数列中，则输出它在数列中的下标；如果不存在，则输出 −1。
输入输出样例
输入 #1复制运行
5 4 10 20 30 40 50 30 10 50 35
输出 #1复制运行
3 1 5 -1
说明/提示
对于所有测试点，保证：
- 1≤n,m≤106
- 1≤ai,q≤109
- 对于 1≤i<n，保证 ai<ai+1。
本题输入输出量较大，请使用较快的 IO 方式。
#include<iostream> using namespace std; const int N = 1e6 + 10; int arr[N]; int Find(int x, int arr[], int n) { int l = 1; int r = n; int m = l + (r - l) / 2; if (arr[l] == x) return l; if (arr[r] == x) return r; while (l <= r) { m= l + (r - l) / 2; if (arr[m] < x) l = m + 1; else if (arr[m] > x) r = m - 1; else return m; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m, q; cin >> n >> m; for (int i = 1;i <= n;i++) cin >> arr[i]; while (m--) { cin >> q; cout << Find(q,arr,n) << endl; } return 0; }2.B2167 查找最后一个出现的位置
题目描述
输入一个长度为 n 的非递减正整数数列 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中最后一次出现的下标。如果序列中不包含该数字，请输出 −1 。
注意：下标从 1 开始。
输入格式
第一行，包含两个正整数 n 和 m，分别表示数列的长度和询问的次数。
第二行，包含 n 个正整数 a1,a2,…,an。
接下来 m 行，每行包含一个正整数 q，表示一次询问。
输出格式
输出共 m 行。
对于每次询问，如果数字 q 存在于数列中，则输出它在数列中最后一次出现的下标；如果不存在，则输出 −1。
输入输出样例
输入 #1复制运行
8 5 2 3 5 5 5 8 9 9 5 2 9 6 8
输出 #1复制运行
5 1 8 -1 6
说明/提示
样例解释
数列为 [2,3,5,5,5,8,9,9]。
- 询问 5：数字 5 最后一次出现在第 5 个位置。
- 询问 2：数字 2 最后一次出现在第 1 个位置。
- 询问 9：数字 9 最后一次出现在第 8 个位置。
- 询问 6：数列中不存在 6。
- 询问 8：数字 8 最后一次出现在第 6 个位置。
数据范围
对于所有测试点，保证：
- 1≤n,m≤106
- 1≤ai,q≤109
- 对于 1≤i<n，保证 ai≤ai+1。
本题输入输出量较大，请使用较快的 IO 方式。
这题优化到这样已经是我想到的最优了，真想不到别的办法了。主要是我觉得新的下标会覆盖旧的，所以mp里面存的就是最新的下标，而且这肯定比二分快，也就只开了一个数组 。超时也不是内存超限，证明就是快读快写的问题。然后我想过用scanf和printf优化，还想过解除绑定优化，然后还是不成功。
#include<stdio.h> const long long N = 1e9 + 10; int mp[N]; int main() { int n, m, q; scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) { int x; scanf("%d",&x); //新的下标会覆盖旧的 mp[x] = i; } while (m--) { scanf("%d",&q); if (mp[q] > 0) printf("%d\n",mp[q]); else printf("-1\n"); } return 0; }3.P2249 【深基13.例1】查找
题目描述
输入 n 个不超过 109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
输入输出样例
输入 #1复制运行
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6
输出 #1复制运行
1 2 -1
说明/提示
数据保证，1≤n≤106，0≤ai,q≤109，1≤m≤105
本题输入输出量较大，请使用较快的 IO 方式。
#include<iostream> using namespace std; const int N=1e6+10; int arr[N]; const int N1=9e8; int mp[N1*2]; int main() { int n,m,q; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&arr[i]); for(int i=n;i>=1;i--) mp[arr[i]]=i; while(m--) { scanf("%d",&q); if(mp[q]>0) printf("%d ",mp[q]); else printf("-1 "); } return 0; }