题解 P1918 【保龄球】
引领天下
2018-12-16 18:47:14
这题竟然没有C++set的，STL会伤心的QAQ
我先讲一下本题的暴力做法
不解释，读入n个数据，然后对于每个m查找。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100005],q;
int main(){
scanf ("%d",&n);
for (int i=1;i<=n;i++)scanf ("%d",&a[i]);
scanf ("%d",&q);
while (q--){
bool ok=0;
scanf ("%d",&m);
for (int i=1;i<=n&&!ok;i++)if (a[i]==m)ok=printf ("%d\n",i);
if (!ok)printf ("0\n");
}
}
```
非常简单，于是快乐的T了。
观察一下，T的效率瓶颈在于
```
for (int i=1;i<=n&&!ok;i++)if (a[i]==m)ok=printf ("%d\n",i);
```
这里是朴素的查找，最坏会退化到O(n)的级别
那么如何优化呢？
此处分出了2条思路：
# 1.用map搞映射
这玩意相当于开了一个非常大的桶，而且也有题解讲了，我就不多说了
# 2.用STL的lower_bound
首先讲一下为什么用lower_bound。
因为lower_bound是找第一个≥n的元素，所以如果在数组中有n的话一定会找到n。
然后又分出了2条思路：
- 用结构体重载运算符
- 这个也有题解介绍了，我就不说了
- 用set
- 大家都知道，set按第一关键字排序，所以我们可以用结构体的思想，用set维护一个二元组(s,id)，s为具体值，id为行号。接下来就可以愉快地用lower_bound啦~
代码：
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
set<pair<int,int> > st;//新建一个set
int n,m,q,s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);//加速流读入
cin>>n;
for (register int i=1;i<=n;i++){
cin>>s;
st.insert(make_pair(s,i));//插入二元组
}
cin>>q;
while (q--){
cin>>m;
set<pair<int,int> >::iterator it=st.lower_bound(make_pair(m,0));
if (it->first==m)cout<<(it->second)<<endl;//如果能找到m，输出id；
else cout<<0<<endl;//找不到输出0
}
}
```