题解 P1918 【保龄球】

发表于 更新于 阅读次数： Waline：
P1918 【保龄球】题解。

这题竟然没有C++set的，STL会伤心的QAQ

我先讲一下本题的暴力做法

不解释，读入n个数据，然后对于每个m查找。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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的效率瓶颈在于

1
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啦~

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 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
    }
}