每日OJ_牛客_ruby和薯条_排序+二分/滑动窗口_C++_Java

目录

ruby和薯条_排序+二分/滑动窗口

题目解析

C++代码

Java代码

ruby和薯条_排序+二分/滑动窗口

ruby和薯条

描述：

ruby很喜欢吃薯条。
有一天，她拿出了n根薯条。第i根薯条的长度为ai。
ruby认为，若两根薯条的长度之差在l和r之间，则认为这两根薯条有“最萌身高差”。
用数学语言描述，即若l≤|ai-aj|≤r，则第i根薯条和第j根薯条有“最萌身高差”。
ruby想知道，这n根薯条中，存在多少对薯条有“最萌身高差”？
注：次序不影响统计，即认为(ai,aj)和(aj,ai)为同一对。

输入描述：

第一行三个正整数n,l,r，含义见题目描述。 （1≤n≤200000,1≤l≤r≤1e9）
第二行n个正整数ai，分别代表每根薯条的长度。 （1≤ai≤1e9）

输出描述：

一个正整数，代表，代表“最萌身高差”的薯条对数。

题目解析

• 库函数排序+二分

C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0, l = 0, r = 0;
    cin >> n >> l >> r;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];    
    }
    sort(a.begin(), a.end());
    
    long long res = 0;
    for(int i = 0; i < n; ++i) // 二分
    {
        int left = -1, right = -1;
        auto it1 = lower_bound(a.begin(), a.end(), a[i] + l); // 找第一个大于等于a[i] + l的
        left = it1 - a.begin();
        
        auto it2 = upper_bound(a.begin(), a.end(), a[i] + r); // 找第一个大于a[i] + r的
        right = it2 - a.begin() - 1;
        
        if(left != -1 && right != -1 && right >= left)
            res += right - left + 1;
    }
    cout << res << endl;
    
//     int begin = 0, end = 1, res = 0, flag = 0; // 用的滑动窗口，没想到加前缀和，所以错了
//     while(begin < end && end < n)
//     {
//         //cout << begin << " " << end << " res " << a[end] - a[begin] << endl;
//         while(end < n)
//         {
//             //cout << begin << " and " << end << " res " << a[end] << " "<< a[begin] << endl;
//             if(a[end] - a[begin] >= l && a[end] - a[begin] <= r)
//             {
//                 ++res;
//                 if(a[end] - a[begin] == r)
//                     break;
//             }
//             ++end;
//         }
//         ++begin;
// //         end = flag;
//         end = begin + 1;
//     }
    return 0;
}

Java代码

import java.util.*;
public class Main
{
    public static int n, l, r;
    public static int[] arr;

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); l = in.nextInt(); r = in.nextInt();
        arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = in.nextInt();
        Arrays.sort(arr);

        long ret = 0;
        for(int i = 1; i < n; i++)
        {
            int L, R;
            // 找左端点
            int left = 0, right = i - 1;
            while(left < right)
            {
                int mid = (left + right) / 2;
                if(arr[mid] >= arr[i] - r) right = mid;
                else left = mid + 1;
            }
            if(arr[left] >= arr[i] - r) L = left;
            else L = left + 1;
            // 找右端点
            left = 0; right = i - 1;
            while(left < right)
            {
                int mid = (left + right + 1) / 2;
                if(arr[mid] <= arr[i] - l) left = mid;
                else right = mid - 1;
            }
            if(arr[left] <= arr[i] - l) R = left;
            else R = left - 1;
            if(R >= L) ret += R - L + 1;
        }

        System.out.println(ret);
    }
}