wcx_is_god @ 2024-05-07 16:54:07
2.0,样例过了,提交四个WA还有一个TLE。
我真的是栓Q。
废话少说,长话短说,请看代码,写的很烂。
#include<bits/stdc++.h>
using namespace std;
int a[1000005],m,n,q,ans;
//11 1 1 3 3 3 5 7 9 11 13 15 15 3
int f(int q){
int l = 1,r = n,flag = 0,mid;
while(l<r){
mid = (l+r)/2;
if(a[mid] == q){
flag = 1;
break;
}
else if(a[mid] < q) l = mid+1;
else r = mid-1;
}
int i = mid;
if(flag){
while(true){
if(a[i-1] != a[i]) return i;
else i--;
}
}else return -1;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
for(int i = 1; i <= m; i++){
scanf("%d",&q);
ans = f(q);
cout << ans << " ";
}
return 0;
}
by _C_ccx_N_ @ 2024-05-07 17:12:34
二分查找
by HAha20120522 @ 2024-05-07 17:31:45
找到之后不能着急BREAK
#include <bits/stdc++.h>
int a[1000010];
int ans[1000010]={-1};
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n, m,x[1000010];
cin >> n>>m;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i=1;i<=m;i++)
cin >> x[i];
int l = 1, r = n, mid=-1;
for(int i=1;i<=m;i++){
l = 1;
r = n;
ans[i]=-1;
while (l <= r) {
mid = (l + r) / 2;
if (a[mid] == x[i]) { // 如果中间的数字等于要找的
ans[i]=mid; // 记录答案位置
r=mid-1;// 局限在左区间
}
else if (a[mid] > x[i]) // 如果中间数字大于要找的
r=mid-1; // 局限在左区间
else // 如果中间数字小于要找的
l=mid+1; // 局限在右区间
}
}
for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
return 0;
}
@WCX12312