MatchlessLian @ 2024-05-15 23:08:00
求佬帮看,我看了讨论区,有说输出没有加空格,有说没有排序,还有说没有用二分会爆时间,还有说排序后应该带原元素的在初始数组中的编号,我都试了,结果还是wa,明明讨论区一些hack的数据我这也可以正常跑,结果提交还是wa,很奇怪,求佬求佬 本来没有用vector+pair写的,就纯一个一维数组(因为我看题目中是说数据是单调递增的就没管)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 1000005
#define M 100005
int ask[M];
int l,r;
int n,m;
vector< pair<int,int> > num;
bool cmp(pair<int,int> p1,pair<int,int> p2)
{
return p1.first<p2.first;
}
int find(int temp)
{
int ans=-1;
l=1,r=n;
int mid;
while(l<r){
mid=(l+r)/2;
if(temp==num[mid].first)
{ans=num[mid].second;break;}
else if(temp<num[mid].first)
{r=mid;}
else if(temp>num[mid].first)
{l=mid+1;}
}
if(ans!=-1)
{
while(num[mid-1].first==ans)mid--;
return mid;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
int temp;
num.push_back(make_pair(-1,0));
for(int i=1;i<=n;i++)
{
scanf("%d",&temp);
num.push_back(make_pair(temp,i));
}
sort(num.begin(),num.end(),cmp);
for(int i=0;i<m;i++)
scanf("%d",&ask[i]);
for(int i=0;i<m;i++)
{
printf("%d ",find(ask[i]));
}
}