题目描述
DL 算缘分算得很烦闷,所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了,所以技术上不成问题,于是他就想玩点新花招。

DL 的视力真的很不错,竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球,这样就能打倒一定数量的瓶子。

◯◯◯◯◯◯

◯◯◯ ◯◯◯◯ ◯

◯◯

◯ ◯◯ ◯

如上图,每个 “◯◯” 代表一个瓶子。如果 DL 想要打倒 33 个瓶子就在 11 位置发球,想要打倒 44 个瓶子就在 22 位置发球。

现在他想要打倒 mm 个瓶子。他告诉你每个位置的瓶子数,请你给他一个发球位置。

输入格式
第一行包含一个正整数 nn,表示位置数。

第二行包含 nn 个正整数 aiai​ ,表示第 ii 个位置的瓶子数,保证各个位置的瓶子数不同。

第三行包含一个正整数 QQ,表示 DL 发球的次数。

第四行至文件末尾,每行包含一个正整数 mm,表示 DL 需要打倒 mm 个瓶子。

输出格式
共 QQ 行。每行包含一个整数,第 ii 行的整数表示 DL 第 ii 次的发球位置。若无解,则输出 00。

输入输出样例
输入 #1复制

5
1 2 4 3 5
2
4
7
输出 #1复制

3
0
样例解释:查找两个数:4和7,4在第三个位置出现,而7从未出现,输出0。

说明/提示
【数据范围】

对于 50%50% 的数据,1≤n,Q≤1000,1≤ai,m≤10的五次方1≤n,Q≤1000,1≤ai​,m≤10的五次方。

对于 100%100% 的数据,1≤n,Q≤100000,1≤ai,m≤10的9次方1≤n,Q≤100000,1≤ai​,m≤10的9次方。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+50;
int n,a[maxn],q,t;
vector<pair<int,int> >v;
bool cmp(pair<int,int> p1,pair<int,int> p2){    //比较函数
    return p1.second < p2.second;
}
int f(int t){        //手动二分
    int l = 0,r = n;
    while(l < r){
        int mid = l + (r-l)/2;
        if(v[mid].second >= t ){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    if(l == n)
        return 0;
    if(v[l].second == t){
        return v[l].first;
    }
    return 0;
}
int main(){
    //freopen("a.txt","r",stdin);
    cin>>n;
    for(int i = 0;i< n;i++){
        cin>>t;
        pair<int,int> p = make_pair(i+1,t);
        v.push_back(p);
    }
    sort(v.begin(),v.begin()+n,cmp);
    cin>>q;
    for(int i = 0;i< q;i++){
        cin>>t;
        cout<<f(t)<<endl;
    }
    return 0;
}
 

Logo

有“AI”的1024 = 2048,欢迎大家加入2048 AI社区

更多推荐