8 条题解
-
2
万能二分板子，找左右边界即可 PS:记得注意下标嗷
#include <bits/stdc++.h> #define endl '\n' #define int long long #define INF 0x3f3f3f3f3f const int N = 100010; using namespace std; int arr[N]; int n,q,tmp; int bs_left(int arr[],int n,int x){ int l = 0; int r = n+1; while(l+1<r){ int mid = (l+r)/2; if(arr[mid]<x){ l = mid; }else{ r = mid; } } if(arr[r] == x){ return r-1; }else{ return -1; } } int bs_right(int arr[],int n,int x){ int l = 0; int r = n+1; while(l+1<r){ int mid = (l+r)/2; if(arr[mid]<=x){ l = mid; }else{ r = mid; } } if(arr[l] == x){ return l-1; }else{ return -1; } } signed main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i = 1; i<= n;i++){ cin>>arr[i]; } while(q--){ cin>>tmp; int ans_left = bs_left(arr,n,tmp); int ans_right = bs_right(arr,n,tmp); cout<<ans_left<<" "<<ans_right<<endl; } return 0; } -
1
// https://dashoj.com/p/88 #include <bits/stdc++.h> #define N 100010 using namespace std; int n, q, x; vector<int> ls(N, 0); int main() { cin >> n >> q; for (int i = 0; i < n; i++) cin >> ls[i]; while (q--) { cin >> x; int l = 0, r = n - 1, ans = 0; while (l <= r) { int m = (l + r) >> 1; if (ls[m] >= x) { ans = m; r = m - 1; } else l = m + 1; } if (ls[ans] == x) cout << ans << ' '; else { cout << "-1 -1" << endl; continue; } l = 0, r = n - 1, ans = 0; while (l <= r) { int m = (l + r) >> 1; if (ls[m] <= x) { ans = m; l = m + 1; } else r = m - 1; } cout << ans << endl; } return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=100010; int arr[N]; int n,q,tmp; int bs_left(int arr[],int n,int x) { int l=0,r=n+1; while(l+1<r) { int mid=(l+r)/2; if(arr[mid]>=x)//x——正无穷，只能从第一个等于x退出，从右向左往x挤 { r=mid;//在最终检查时，如果 arr[mid] == x，说明 r 正好指向第一个出现 x 的位置 } else { l=mid; } } if(arr[r]==x) { return r-1; } else { return -1; } } int bs_right(int arr[],int n,int x) { int l=0,r=n+1; while(l+1<r) { int mid=(l+r)/2; if(arr[mid]<=x)//负无穷——x，只能从最后一个x退出，从左向右往x挤 { l=mid;//在最终检查时，如果 arr[mid] == x，说明 l 正好指向最后一个出现 x 的位置 } else { r=mid; } } if(arr[l]==x) { return l-1; } else { return -1; } } int main() { cin>>n>>q; for(int i=1;i<=n;i++) { cin>>arr[i]; } while(q--) { cin>>tmp; int ans_left=bs_left(arr,n,tmp); int ans_right=bs_right(arr,n,tmp); cout<<ans_left<<" "<<ans_right<<endl; } return 0; } -
0
#include <iostream> #include <vector> using namespace std;
pair<int, int> findRange(const vector<int>& arr, int target) { int n = arr.size(); int left = -1, right = -1;
// 寻找起始位置 int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else if (arr[mid] > target) { high = mid - 1; } else { left = mid; high = mid - 1; // 继续寻找左边界 } } // 寻找终止位置 low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] < target) { low = mid + 1; } else if (arr[mid] > target) { high = mid - 1; } else { right = mid; low = mid + 1; // 继续寻找右边界 } } return {left, right};}
int main() { int n, q; cin >> n >> q;
vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } for (int i = 0; i < q; ++i) { int target; cin >> target; pair<int, int> result = findRange(arr, target); cout << result.first << " " << result.second << endl; } return 0;}
-
0
#include <bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, q; cin >> n; cin >> q; vector<ll> q_arr(q); vector<ll> a(n); ll index_begin, index_end; for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < q; ++i) { cin >> q_arr[i]; } for (ll q_i : q_arr) { auto it_l = lower_bound(a.begin(), a.end(), q_i); if (it_l == a.end() or (*it_l != q_i)) { printf("-1 -1\n"); } else { index_begin = distance(a.begin(), it_l); index_end = distance(a.begin(), upper_bound(it_l, a.end(), q_i))-1; printf("%lld %lld\n", index_begin, index_end); } } return 0; } -
0
用python做的,前面一部分判断在最左边和最右边的情况，然后分析不在边界的情况，用二分法找到其中一个值的时候，再用循环分别向前找和向后找并记录位置
n,q = map(int,input().split()) num_list = list(map(int,input().split())) quest_list=[] def check(num): global num_list begin = 0 end = len(num_list) - 1 pos_begin = 0 pos_end = 0 flag = True if num_list[begin] == num: flag = False count = 0 pos_begin = 0 while (num_list[count] == num): pos_end = count count += 1 elif num_list[end] == num: flag = False count = len(num_list) - 1 pos_end = len(num_list) - 1 while (num_list[count] == num): pos_begin = count count -= 1 else: while((end - begin) != 1): middle = (begin + end) // 2 if num > num_list[middle]: begin = middle elif num <num_list[middle]: end = middle else: flag = False count1 = middle count2 = middle while(num_list[count1] == num): pos_begin = count1 count1 -= 1 while(num_list[count2] == num): pos_end = count2 count2 += 1 break if flag: pos_begin = -1 pos_end = -1 print(pos_begin,pos_end) for i in range(q): quest_list.append(int(input())) for quest_num in quest_list: check(quest_num) -
0
Python调库
import sys import bisect input = sys.stdin.readline n, q = map(int, input().split()) d = list(map(int, input().split())) for _ in range(q): num = int(input()) if num < d[0] or num > d[-1]: print(-1, -1) continue left = bisect.bisect_left(d, num) if d[left] != num: print(-1,-1) continue right = min(bisect.bisect_right(d, num), n-1) if d[right] != num: right-=1 print(left,right) -
0
一种全新的思路来解决二分问题
不需要仔细思考边界问题
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<string> using namespace std; int n,q; const int N=100010; int nums[N]; int front_find(int target){ int l=-1,r=n; while(l+1!=r){ int mid=l+r>>1; if(nums[mid]<target) l=mid; else r=mid; } if(r==n || nums[r]!=target) return -1; else return r; } int end_fond(int target){ int l=-1,r=n; while(l+1!=r){ int mid=l+r>>1; if(nums[mid]>target) r=mid; else l=mid; } if(l==-1 || nums[l]!=target) return -1; else return l; } void slove(){ int target; cin>>target; int l=front_find(target); if(l!=-1){ int r=end_fond(target); cout<<l<<" "<<r<<endl; } else cout<<"-1 -1"<<endl; } int main(){ cin>>n>>q; for(int i=0;i<n;i++) scanf("%d",&nums[i]); while(q--) slove(); return 0; }
- 1
