X02day2
2025-07-28 19:50:22
发布于：浙江
8阅读
0回复
0点赞
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N];
// 二分查找 有序序列a[l,r]中查找x
int BinarySearch(int a[], int l, int r, int x) {
while(l<=r){
int mid=(l+r)/2;
if(a[mid]==x){
return mid;
}else if(a[mid]>x)r=mid-1;
else if(a[mid]<x)l=mid+1;
}
return -1;
}
int main() {
int n, q, m, x;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (q--) {
cin >> x;
// a[1]~a[n]中查找x存在的位置
int p = BinarySearch(a, 1, n, x);
cout << p<<endl;
}
return 0;
}
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int main() {
int n, q, x;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (q--) {
cin >> x;
int ans = n + 1;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] <= x) {
ans=mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << "\n";
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,q;
cin>>n>>q;
int a[1000005];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=q;i++){
int ans=-1;
int t;
cin>>t;
int l=1,r=n;
while(l<=r){
int m=(l+r)/2;
if(a[m]<=t){
ans=m;
l=m+1;
}else{
r=m-1;
}
}if(a[ans]==t)cout<<ans<<endl;
else cout<<-1<<endl;
}
}
#include <bits/stdc++.h>
using namespace std;
int n,q;
int a[100005];
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=q;i++){
int t;
cin>>t;
int ans=0;
int s=lower_bound(a+1,a+n+1,t)-a;
int x=upper_bound(a+1,a+n+1,t)-a;
int d=x-s;
cout<<n-d<<endl;
}
}
/*前缀和：原数组前i个数之和
s[1]=a[1]
s[2]=a[1]+a[2]
s[3]=a[1]+a[2]+a[3];
`
`
`
s[n-1]=a[1]+a[2]+...+a[n-1]
s[n]=a[1]+a[2]+...+a[n]
对应预处理：
s[i]=s[i-1]+a[i]
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
差分数组：原数组相邻两数之差
d[i]=a[i]-a[i-1];
for(int i=1;i<=n;i++){
d[i]=a[i]-a[i-1];
}
前缀和：求区间l，r
a:1 2 3 4 5
s:1 3 6 10 15
sum(2,4)=s[4]-s[1]
O(1)
sum(l,r)=s[r]-s[l-1];
差分的应用：
1.求原数组（前缀和）
a:1 2 3 4 5
d:1 1 1 1 1
s:1 2 3 4 5(对差分数组求前缀和得到原数组)
2.做多次区间修改
对区间[l,r]所有的数加上c
a:1 2 3 4 5
d:1 1 1 1 1
a:1 2+c 3+c 4+c 5
d:1 1+c 1 1 1-c
d[l]+=c
d[r+1]-=c
求前缀和得到对应原数组
*/
/*int upp(int a[]，int l,int r,int x){
int ans=r+1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>x){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}return ans;
}*/
/*
int N,A[200005],B,C;
int main(){
cin>>N>>C;
for(int i=1;i<=N;i++){
cin>>A[i];
}
int cnt=0;
sort(A+1,A+N+1);
for(int i=1;i<=n;i++){
B=A[i]+c;
int x,y;
cnt+=upper_bound(A+1,A+N+1,B)-lower_bound(A+1,A+N+1,B);
}cout<<cnt;
}
*/
#include <bits/stdc++.h>
using namespace std;
struct S {
string No;
string name;
bool nn;
int age;
}a[1e5+10];
bool cmp(S a,S b){
a.id<b.id;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i].id>>arr[i].name>>arr[i].x>>arr[i].age;
}sort(a+1,a+n+1);
int q;
cin>>q;
while(q--){
string x;
cin>>x;
int l=1,r=n;
int ans=-1;
while(l<=n){
int mid(l+r)/2;
if(a[mid].No==x){
ans=mid;
break;
}
}else if(x>a[mid].No){
l=mid+1;
}
else if(x<a[mid].No){
r=mid-1;
}
if(ans==-1)cout<<"No Answer!";
else cout<<a[ans].No<<" "<<a[ans].name<<" "<<a[ans].nn<<" "<<a[ans].age<<endl;
}
}
#include<bits/stdc++.h>
using namespace std;
int N,A[200005],B,C;
int main(){
cin>>N>>C;
for(int i=1;i<=N;i++){
cin>>A[i];
}
int cnt=0;
sort(A+1,A+N+1);
for(int i=1;i<=N;i++){
B=A[i]+C;
int x,y;
cnt+=upper_bound(A+1,A+N+1,B)-lower_bound(A+1,A+N+1,B);
}cout<<cnt;
}
这里空空如也
有帮助，赞一个