11 条题解

  • 2
    @ 2024-4-9 16:17:23

    万能二分板子，找左右边界即可 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
      @ 2025-1-19 0:01:38 
      // 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
        @ 2025-3-31 17:17:34

        #include <iostream> using namespace std;

        const int N = 1e5 + 10;

        int a[N]; int n, q;

        int main() { cin.tie(0); cout.tie(0);

        cin >> n >> q;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}

while (q--) {
    int x;
    cin >> x;
    int l = 1, r = n;
    int ans;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= x) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    if (a[ans] != x) {
        cout << "-1 -1" << endl;
        continue;
    }

    cout << ans - 1 << " ";

    l = 1, r = n, ans = 1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans - 1  << endl;
}

return 0;

        }

        • 0
          @ 2025-3-18 20:21:36

          #include <bits/stdc++.h> using namespace std; #define int long long int a[100005],n,q,i,x,j,h; int check(int m,int l,int r) { ** if(l>r)** return -1; ** int mid=(l+r)/2;** ** if(m==a[mid])** return mid; ** else if(m<a[mid])** ** return check(m,l,mid-1);** ** else ** return check(m,mid+1,r); } signed main() { ** cin>>n>>q;** ** for(i=0;i<n;i++)** ** cin>>a[i];** ** for(i=0;i<q;i++)** ** { ** cin>>x; ** int t=check(x,0,n-1);** ** if(t>=0)** ** { ** for(j=t+1;j<n;j++) ** { ** if(a[j]!=a[t]) ** break;** ** } ** for(h=t-1;h>=0;h--) ** { ** if(a[h]!=a[t]) ** break;** ** } ** cout<<h+1<<' '<<j-1<<endl; ** } ** else ** cout<<-1<<' '<<-1<<endl;** ** } ** return 0; }

          • 0
            @ 2025-3-15 18:10:37 
            #include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> PII;  
using ll = long long;
using ULL = unsigned long long;
const int N = 1e6+5;

int n, q;
int a[N];
inline void solve() { 
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (; q-- ;) {
        int x; cin >> x;
        int l = 0 ,r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        } 
        if (a[l] != x) cout << "-1 -1" << endl;
        else {
            cout << l << ' ';
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= x) l = mid;
                else r = mid - 1; 
            }
            cout << l << endl;
        }
    }
}          

int main() { 
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1; 
    //int _; cin >> _;
    while (_--) solve();
    return 0;
}
            • 0
              @ 2025-2-10 19:18:16 
              #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
                @ 2024-4-20 12:33:48

                #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
                  @ 2024-4-12 19:54:21 
                  #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
                    @ 2024-4-11 15:41:29

                    用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
                      @ 2024-4-10 22:55:37

                      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
                        @ 2024-4-10 20:16:51

                        一种全新的思路来解决二分问题

                        不需要仔细思考边界问题

                        #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

                        数的范围

                        信息

                        ID
                        88
                        时间
                        1000ms
                        内存
                        256MiB
                        难度
                        7
                        标签
                        递交数
                        1250
                        已通过
                        290
                        上传者
                        1. 兼容模式
                        2. © 2024-2028 Dashcoding
                        3. 粤ICP备2024204050号-1
                        4. Powered by Hydro