题解：P1918 保龄球

· · 题解

题意

给定 n 个位置，每个位置有 a_i 个保龄球，想要打倒 m 个瓶子，问在哪发球。

结构体排序+二分查找

结构体内应该有两个变量，分别代表什么位置和此位置有多少瓶子。

代码就是：

struct baoling{
   int pos;  //位置
   int sum;  //有多少个瓶子
}

随后我们要定义一个结构体数组来存储数据。

在输入数据结束后，要进行查找，因为顺序查找的 O\left(n \right) 太慢了，所以考虑进行二分查找。

注：二分查找的时间复杂度是 O\left(\log n \right) 。

注意到，因为二分查找需要排序，所以要在查找前先把这个结构体数组进行排序，排序规则就是从小到大。代码就是：

bool cmp(baoling a,baoling b){
   return a.sum<b.sum;
}

然后我们知道 STL 中有一个快速排序函数 sort ，那么我们直接使用这个 sort 函数进行排序就行了。代码就是：

sort(arr+1,arr+n+1,cmp);

注：这个排序的数组的数据是从下标 1 开始存的。这个快速排序的 sort 函数时间复杂度为 O\left(n \log n \right) 。

最后在循环里面进行二分查找并输出就行了。

说一下复杂度：

  1. 输入部分：输入循环 n 次，时间复杂度 O\left(n \right) 。

  2. 排序部分：使用 sort 函数快速排序，时间复杂度 O\left(n \log n \right) 。

  3. 二分部分：使用了 Q 次时间复杂度 O\left(\log n \right) ，时间复杂度为 O\left(Q \times \log n \right) 。

总复杂度为：

O\left(n \right)+O\left(n \log n \right)+O\left(Q \times \log n \right)=O\left(n+n \log n+Q \times \log n \right)

Code:

#include<bits/stdc++.h>
using namespace std;

struct baoling{
    int pos;
    int sum;
};
baoling a[100005];

bool cmp(baoling a,baoling b){
    return a.sum<b.sum;
}

int main(){
    int n;
    cin >>n;
    for(int i=1;i<=n;i++){
        cin >>a[i].sum;
        a[i].pos=i;
    }
    sort(a+1,a+n+1,cmp);
    int q;
    cin >>q;
    for(int i=1;i<=q;i++){
        int l=1,r=n,mid,ans=0;
        int m;
        cin >>m;
        while(l<=r){
            mid=(l+r)/2;
            if(m>a[mid].sum){
                l=mid+1;
            }
            else if(m<a[mid].sum){
                r=mid-1;
            }
            else{
                ans=a[mid].pos;
                break;
            }
        }
        cout <<ans<<endl;
    }
    return 0;
}

映射

STL 中有一个容器名叫 map ，就是映射，这道题目也可以用这个来做。

首先，定义一个 map ，代码为：

map<int,int> mmap;

然后正常输入就行。输入完 Q 后，可以写一个循环，循环 Q 次。在循环内部，每次输入一个目标变量。随后如果 map 中有这个元素，那么输出，否则输出 0 即可。

时间复杂度还是分部分讨论：

  1. 输入部分，还是 O\left(n \right) 。

  2. 获取答案部分：因为 count 函数是 O\left(\log n \right) ，所以复杂度为 O\left(Q \times \log n \right) 。

总复杂度为：O\left(n+Q \times \log n \right) ，总体来说比结构体快一点。

Code:

#include<bits/stdc++.h>
using namespace std;

map<int,int> mmap;

int main(){
    int n;
    cin >>n;
    for(int i=1;i<=n;i++){
        int t;
        cin >>t;
        mmap[t]=i;
    }
    int q;
    cin >>q;
    while(q--){
        int target;
        cin >>target;
        if(mmap.count(target)){
            cout <<mmap[target]<<endl;
        }
        else{
            cout <<0<<endl;
        }
    }
    return 0;
}

总结

这道题有以下坑点：