求大佬帮帮忙啊啊啊啊啊
查看原帖
求大佬帮帮忙啊啊啊啊啊
361505
Escapism楼主2021/8/23 23:23

二分,84分,第一个点

代码在这了(带注释)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1e6 + 15;
long long a[MAXN];
int n,k;

int check(int x,int t){ 
	if (a[x] > t)return 0; //大了
	else if (a[x] < t)return 1; //小了
	else if (a[x] == t && a[x - 1] == t) return 2; //相等,非第一
	else if (a[x] == t && a[x - 1] < t) return 3;//找到了
}

int main(){
	scanf("%d %d",&n,&k);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		
	//输入不必多说
		
	for (int i = 1;i <= k;i++){
		long long t;
		cin>>t;
		long long l = 0, r = n + 1,mid;
		//二分
		while (l < r) {
			mid = (l+r+1) / 2;
			//cout<<mid<<" ";
			if (check(mid,t) == 0 || check(mid,t) == 2) //大了 或是相等但不是最前面
				r = mid - 1;
			else if (check(mid,t) == 1) //小了
				l = mid;
			else if (check(mid,t) == 3) break; //找到了
			//cout<<check(mid,t)<<endl;
			
		}
		if (check(mid,t) == 3) //判断一下
			printf("%d ",mid);
		else
			printf("-1 ");
	}
	return 0;
}
2021/8/23 23:23
加载中...