魂逝_秦月歌 @ 2023-09-11 13:28:50
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <cctype>
#include <queue>
#include <deque>
#include <ctime>
#include <cstring>
#include <string>
#define _e putchar (' ')
#define _v putchar ('\n')
#define ll long long
#define INF 999999999999999999ll
#define INE -999999999999999999ll
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
inline int lowbit (int x) {
return x&(-x);
}
inline int mx(int x,int y) {
return x>y?x:y;
}
inline int mn(int x,int y) {
return x<y?x:y;
}
inline void rd(int &x) {
int s=0,w=1;
char ch=getchar ();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar ();}
while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+(ch^48); ch=getchar ();}
x=s*w;
}
inline void wr(int x) {
if(x<0) x=-x,putchar (45);
if(x<10) {
putchar (x+48);
return ;
}
wr(x/10);
putchar (x%10+48);
}
inline int ab (int x) {
if(x<0) return -x;
return x;
}
inline void swap (int &x,int &y) {
x^=y^=x^=y;
}
const int N=1000005;
int n,m,k,mid,a[N];
inline bool check (int x) {
if (a[x]<k) return 1;
return 0;
}
inline int binary_search () {
int lt=0,rt=n;
while (lt<rt) {
mid=(lt+rt)>>1;
if (check (mid)) lt=mid+1;
else rt=mid;
}
if(a[mid+1]==k) return (mid+1);
else return -1;
}
int main () {
rd(n),rd(m);
for (int i=1;i<=n;i++) rd(a[i]);
sort(a+1,a+1+n);
for (int j=1;j<=m;j++) {
rd(k);
wr(binary_search()),_e;
}
return 0;
}
//求助哪里有问题
by zacharyzhong @ 2023-09-11 13:34:58
大佬思路没看懂,给个弱智的方法
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000009];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1,x;i<=m;i++)
{
cin>>x;
int p=lower_bound(a+1,a+n+1,x)-a;
if(a[p]!=x)
cout<<"-1 ";
else cout<<p<<' ';
}
return 0;
}
by fengyongrui @ 2023-09-14 19:39:48
1.将62行
int lt=0,rt=n;
改为:
int lt=1,rt=n;
2.将68行
if(a[mid+1]==k) return (mid+1);
改为:
if(a[lt]==k) return lt;
更改后代码:
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <cctype>
#include <queue>
#include <deque>
#include <ctime>
#include <cstring>
#include <string>
#define _e putchar (' ')
#define _v putchar ('\n')
#define ll long long
#define INF 999999999999999999ll
#define INE -999999999999999999ll
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;
inline int lowbit (int x) {
return x&(-x);
}
inline int mx(int x,int y) {
return x>y?x:y;
}
inline int mn(int x,int y) {
return x<y?x:y;
}
inline void rd(int &x) {
int s=0,w=1;
char ch=getchar ();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar ();}
while(ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+(ch^48); ch=getchar ();}
x=s*w;
}
inline void wr(int x) {
if(x<0) x=-x,putchar (45);
if(x<10) {
putchar (x+48);
return ;
}
wr(x/10);
putchar (x%10+48);
}
inline int ab (int x) {
if(x<0) return -x;
return x;
}
inline void swap (int &x,int &y) {
x^=y^=x^=y;
}
const int N=1000005;
int n,m,k,mid,a[N];
inline bool check (int x) {
if (a[x]<k) return 1;
return 0;
}
inline int binary_search () {
int lt=1,rt=n;//改动1
while (lt<rt) {
mid=(lt+rt)>>1;
if (check (mid)) lt=mid+1;
else rt=mid;
}
if(a[lt]==k) return lt;//改动2
else return -1;
}
int main () {
rd(n),rd(m);
for (int i=1;i<=n;i++) rd(a[i]);
sort(a+1,a+1+n);
for (int j=1;j<=m;j++) {
rd(k);
wr(binary_search()),_e;
}
return 0;
}
by 魂逝_秦月歌 @ 2023-10-08 09:33:33
okok感谢,我三年没碰了都忘了