目錄
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);}
}
)
