aaa,求求大佬,为什么一直wa,各种各样改结果还是全wa
查看原帖
aaa,求求大佬,为什么一直wa,各种各样改结果还是全wa
995760
MatchlessLian楼主2024/5/15 23:08

求佬帮看,我看了讨论区,有说输出没有加空格,有说没有排序,还有说没有用二分会爆时间,还有说排序后应该带原元素的在初始数组中的编号,我都试了,结果还是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]));
	}
}
2024/5/15 23:08
加载中...