2024.6.2练习情况—整数二分

#include

#include

using namespace std;

const int N = 100100;

int n,q,k;//题中变量

int arr[N];

//找左端点

void querryleft(int arr[],int k){

        int l=0,r=n-1;

        while(l

                int mid=(l+r)/2;

                if(arr[mid] >= k){

                        r=mid;

                }

                else l=mid+1;

        }

        if(arr[l]==k){

                printf("%d ",l);

        }     

        else printf("-1 ");

        return;

}

//找右端点

void querryright(int arr[],int k){

        int l=0,r=n-1;

        while(l

                int mid=(l+r+1)/2;

                if(arr[mid] <= k){

                        l=mid;

                }

                else r=mid-1;

        }

        if(arr[l]==k){

                printf("%d\n",l);

        }     

        else printf("-1\n");

        return;

}

int main()

{

        cin>>n>>q;

        for(int i=0;i

                scanf("%d",&arr[i]);

        }

        while(q--){

                cin>>k;

                //要求左端点和右端点，若不存在则输出-1

                querryleft(arr,k);

                querryright(arr,k);

        }

        return 0;

}

//代码2：左端点绿色

int l=0,r=n;

while(l

    int mid = l+r >> 1;

    if(check()){

        r = mid;

    }

    else l = mid + 1;

}

//代码2：右端点

int l=0,r=n;

while(l < r){

    int mid = (l+r+1) >> 1;

    if(check()){

        l = mid;

    }

    else r = mid - 1;

}

#include

#include

using namespace std;

const int N = 100000010;

int n,q,k;//题中变量

int arr[N];

void querryleft(int arr[],int k){

        int l=0,r=n-1;

        while(l

                int mid=(l+r)/2;

                if(arr[mid] >= k){

                        r=mid;

                }

                else l=mid+1;

        }

        if(arr[l]==k){

                printf("%d ",l+1);

        }     

        else printf("-1 ");

        return;

}

int main()

{

        cin>>n>>q;

        for(int i=0;i

                scanf("%d",&arr[i]);

        }

        while(q--){

                cin>>k;

                //要求左端点，若不存在则输出-1

                querryleft(arr,k);

        }

        return 0;

 }

#include

#include

using namespace std;

long long n,c;

long long a[100000000];

long long nums[1000010];

long long cnt;

int main()

{

        scanf("%lld%lld",&n,&c);

        for(int i=0;i

                scanf("%d",&a[i]);

    nums[a[i]] ++;

        }

        sort(a,a+n);

        for(int i=0;i

                                cnt += nums[a[i] + c];

        }

        printf("%lld",cnt);

        return 0;

 } 

#include

#include

#include

using namespace std;

const int N = 200010;

long long ans = 0;

int arr[N];

int n,c;

//找左端点

int solve1(int x) {

        int l = 1, r = n;

        while (l < r) {

                int mid = (l + r)/2;

                if (arr[mid] >= x) r = mid;

                else l = mid + 1;

        }

        if (arr[l] != x)return -1;

        return l;

}

//找右端点

int solve2(int x) {

        int l = 1, r = n;

        while (l < r) {

                int mid = (l + r + 1)/2;

                if (arr[mid] <= x) l = mid;

                else r = mid - 1;

        }

        if (arr[l] != x) return -1;

        return l;

}

int main() {

        cin>>n>>c;

        for (int i = 1; i <= n; i++) {

                cin>>arr[i];

        }

        sort(arr + 1, arr + 1 + n);

        for (int i = 1; i <= n; i++) {// 因为不同位置的数字一样的数对算不同的数对

                int x = arr[i] - c;

                if (x < 1) continue;//如果满足条件的x小于1，则说明不x在数列中

                int l = solve1(x);

                if (l == -1) continue;//如果在数列中 不存在x使得a[i]-x=c,就continue

                int r = solve2(x);

                int len = r - l + 1;

                ans += len;

        }

        printf("%lld\n", ans);

        return 0;

}