一、题目
时间限制：500ms
空间限制：64MB
很久以前，有位同学，在学完算法课的二分后，激动的振臂高呼：“我学会二分了！”。此时，一位学长从旁边经过听到此话，决定出一道题考考他，挫挫同学的锐气，让这位学弟再去好好刷二分.
学长告诉学弟n个数据，再询问他q次，每次询问告诉学弟一个x，要求学弟在每次询问给出的x的下标。
二、解题思路
那么我们该怎么根据值找下标呢，如果能做到一对一映射，每个值对应一个下标，实际上map可以做到
这个事情，也就是所谓的哈希。但是顺序是乱序，不能进行二分查找（二分查找的前提是顺序）
当然如果不使用map，我们可以尝试把无序的序列变成有序的，这时候查找值，我们就可以采取二分查找，那下标咋办呢，把下标和值绑定在一起就行，开个结构体存下标和值，排序的时间复杂度是 nlog^n ，二分查找的时间复杂度也是 nlog^n ，时间复杂度也在允许范围之内。值得注意的是，数据范围在 long long 之内，注意别爆 int 了（三年ACM一场空，不开longlong见祖宗）
三、源码及注释
#include<iostream> #include<string> #include<cstdio> #include<algorithm>//sort函数的头文件 using namespace std; const long long N = 1e6 + 5;//满足题目对n的要求，并且稍微开大一点（+5） typedef long long ll;//重新定义long long类型，更加方便 ll n, q, x; struct node { ll idx, num; }arr[N];//创建结构体存储数组中的值和下标 bool cmp(node x, node y) { return x.num < y.num; }//自定义数组元素排序方法 int main() { scanf("%lld%lld", &n, &q);//当数据过多时，不采用cout/cin函数，采用scanf和printf函数 for (int i=1;i<=n;i++) { scanf("%lld", &arr[i].num);//注意long long的打印格式 arr[i].idx = i; } sort(arr+1, arr + n+1,cmp); for (int i=1;i<=q;i++) { scanf("%lld", &x); ll left = 1; ll right = n; ll mid = 0; while (right >= left) { mid = (left + right) / 2; if (arr[mid].num > x) { right=mid-1;//注意最基本的二分查找 } else if (arr[mid].num < x) { left=mid+1; } else { break; } } if (left <= right) { printf("%lld\n", arr[mid].idx); } } return 0; }
