每日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);}
}