第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N个建筑物的的位置,每个位置用一个整数(取值区间为[0, 1000000])表示,从小到大排列(将字节跳动大街看做一条数轴)
一个数字,表示不同埋伏方案的数量。结果可能溢出,请对 99997867 取模
4 3 1 2 3 4
4
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
5 19 1 10 20 30 50
1
可选方案 (1, 10, 20)
2 100 1 102
0
无可选方案
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { final static int MOD = 99997867; public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); // 建筑物数量。 int D = in.nextInt(); // 最大距离。 List<Integer> building = new ArrayList<>(); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case building.add(in.nextInt()); } calNum(N, D, building); } // 枚举左边的位置 : md 看错题了, 我还以为是,相邻不能超过D static void calNum(int N, int D, List<Integer> building) { long[] right = new long[N]; Arrays.fill (right, N-1); Queue<Integer> queue = new LinkedList<>(); queue.add(0); for (int i = 1; i < N; i ++) { while (!queue.isEmpty() && (building.get(i) - building.get(queue.peek())) > D) { right[queue.poll()] = i-1; // 右侧最远距离。 } queue.add(i); } long res = 0; for (int i = 0; i < N; i++) { long n = right[i] - i; if (n >= 2) { res += (n*n-n)/2; res %= MOD; } } System.out.println(res); } }
在这个问题中,我们需要从一组有序的正整数中选出三个数,使它们互相的差值小于等于给定的数d。如果我们从这些数中选出三个数,那么它们中间必然存在两个数的差值小于等于d,而我们需要计算所有符合这个条件的三元组个数。
我们可以从给定的有序数列中每个数开始,寻找符合条件的三元组个数。假设当前数的下标为i,我们需要在从i开始到n-1的范围内寻找最大的下标j,使得pos[j]-pos[i]<=d。然后我们可以计算出从i到j之间的符合条件的三元组个数。而在从i开始到j之间的三元组中,任意选取两个数的差值肯定小于等于d,因此我们只需要在这个区间中任意选取两个数,计算选法数目即可。而选取两个数的选法数目,就是从这个区间中选取两个数的组合数,即C_{2}^{j-i-1}。注:不包括i在内,所以是2
(1)这段代码使用 Collections.binarySearch() 方法在 pos 数组中查找第一个大于 pos.get(i) + d 的元素的位置,如果找到了则返回该位置的下标,否则返回负数,这个负数的值是插入该元素时应该放置的位置的相反数再减一。
(2)当在有序列表 pos 中找不到大于 pos.get(i) + d 的元素时,Collections.binarySearch() 方法返回负数值,而这段代码将这个负数值转换为对应的插入点(即若将 pos.get(i) + d 插入到 pos 中,应该插入的位置),然后将插入点再减1,得到第一个小于等于 pos.get(i) + d 的元素的下标 index。这个下标是用来计算符合要求的三元组数量的。
(3)这段代码是在计算符合条件的三元组数量,其中 (index - i) >=2的用来判断能否从以i为起点,找到至少3个元素其中index是通过二分查找得到的,表示在当前位置i之后第一个差值大于d的位置。
(index - i - 1) * (index - i) / 2的含义是从当前位置i到index-1之间取两个数的组合数,即从index - i - 1个数中选2个数的组合数。这里采用的是组合数公式:C_{m}^{n}=\frac{m!}{n!(m-n)!},即从n个数中选取m个数的组合数。在一组符合要求的数中,任意选取两个数将它们两者间的差值小于等于d的条件都满足,因此选取任意两个数都是合法的方案。
因此,(index - i - 1) * (index - i) / 2就等价于C_{index - i - 1}^{2},表示从index - i - 1个数中选2个数的组合数。
最后,由于可能出现比较大的结果,需要对结果取模,防止溢出。这里取模数为99997867。
import java.util.Scanner; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String input1[] = in.nextLine().split(" "); int n =Integer.parseInt(input1[0]); int d =Integer.parseInt(input1[1]); input1 = in.nextLine().split(" "); //int arr[] = new int[input1.length]; TreeMap<Integer,Integer> map = new TreeMap<Integer, Integer>(); //TreeSet<Integer> set = new TreeSet<>(); for (int i=0;i<input1.length;i++){ //arr[i]=Integer.parseInt(input1[i]); int num = Integer.parseInt(input1[i]); if (map.containsKey(num)){ continue; } map.put(num,i); } long res= 0; Set<Integer> set = map.keySet(); int begin = 0; for (Integer integer : set) { if (begin>=n-2){ break; } int limit = integer+d; Integer floor = map.floorKey(limit); Integer index = map.get(floor); res+=((index-begin)*(index-begin-1))/2; res%=99997867; begin++; } System.out.println(res); } }为什么过不了最后两个用例啊?感觉写的没问题啊
考点:排列组合,同时利用“定一计算二”的方式即可,即总共只有三个数字去排列,所以可以将最右边的固定下,左边两位通过组合的计算公式就可以得出,当然左边两位的边界还需要进行一些判断
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); long num = in.nextInt(); if(num<3){ System.out.println(0); return; } int dis = in.nextInt(); List arr = new ArrayList(); int i=0; while(i++<num) { arr.add(in.nextInt()); } int left = 0; int right = 2; long count = 0; while(right != num){ int curDis = arr.get(right)-arr.get(left); if(curDis <= dis) { if(right-left > 1){ count+=C(right-left); right++; } else{ right++; } }else if(curDis > dis){ if(right-left > 1){ left++; } else{ break; } } } System.out.print(count%99997867L); } public static long C(long num){ if(num == 2)return 1L; return num*(num-1)/2; } }
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n, d; n = sc.nextInt(); d = sc.nextInt(); int[] a = new int[n+1]; for (int i = 0 ; i < n; i++){ a[i] = sc.nextInt(); } // 从左到右会超时,因为右节点有回头,每一次都需要j重置到i+1的位置。 // run_left(n, d, a); // 改用从右到左判断,i每次向后移,j必定在当前值的基础上进行移动。即以最右边的节点作为“定点” run_right(n, d, a); } public static void run_right(int n, int d, int[] a) { Long result = 0L; for (int i = 2, j = 0 ; i < n; i++){ while(a[i] - a[j] > d) { // 因为即使 a[i] - a[i-1] >d, 当j==i 的时候,不满足 a[i] - a[j] > d 的条件 // 所以这里不会使 j > i j++; } // 两者想乘可能会 超过 int 的返回,导致结果为负,输出的结果错误 result += ((long)(i-j)*(long)(i-j-1)/2); } System.out.println(result % 99997867); } public static void run_left(int n, int d, int[] a) { Long result = 0L; for (int i = 0 ; i < n-2; i++){ int j = i + 1; while(j+1 < n && a[j+1] - a[i] <= d) { j++; } result += ((j-i)*(j-i-1)/2); } System.out.println(result % 99997867); } }
import java.util.Scanner; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int d = scanner.nextInt(); int n=scanner.nextInt(); int [] a=new int[d]; for (int i = 0; i < d; i++) { a[i]=scanner.nextInt(); } //定义计数器 int count=0; //遍历,1号位定位 for (int i = 0; i <d-2 ; i++) { //遍历,2号位定位 for(int j=i+1;j<d-1;j++){ //三号位, for (int k=j+1;k<d;k++){ if (a[k]-a[i]<=n){ count++; } } } } System.out.println(count%99997867); }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @Author: JiaJianpeng * @Date: 2020-05-06 9:08 * @Description: com.t2019.字节跳动 * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line1[] = br.readLine().split(" "); int N = Integer.valueOf(line1[0]); int D = Integer.valueOf(line1[1]); String line2[] = br.readLine().split(" "); int loc[] = new int[N]; for (int i = 0; i < N; i++) loc[i] = Integer.valueOf(line2[i]); long res = 0; for (int i = 0;i <= N-3; i++){ res += bs(i, loc, N-1, D); if (res >= 99997867) res %= 99997867; } System.out.println(res); } private static long bs(int target, int[] loc, int r, int D) { int l = target + 2; int mid; long res; while (l <= r){ mid = (l + r) >>1; if (loc[mid] - loc[target] <= D) l = mid + 1; else r = mid - 1; } res = r - target; return res >= 2? res*(res-1)/2: 0; } }方法二:滑动窗口
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @Date: 2020-05-06 10:07 * @version: 1.0 */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line1[] = br.readLine().split(" "); int N = Integer.valueOf(line1[0]); int D = Integer.valueOf(line1[1]); String line2[] = br.readLine().split(" "); int loc[] = new int[N]; for (int i = 0; i < N; i++) loc[i] = Integer.valueOf(line2[i]); long count = 0L; int right = 2; for(int i = 0; i< N-2; i++){ long temp=0L; int j = right; for(; j < N && loc[j] - loc[i] <= D; j++); temp = j - 1 - i; if(temp >= 2) count += temp * (temp-1) / 2; if (count >= 99997867) count %= 99997867; right = j; } System.out.println(count); } }两种方法耗时差不多。。。,但坐标位置均匀分布的话,可以初次查找用二分,后面再用滑动窗口,这样耗时应该比较少。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); int D = input.nextInt(); int[] L = new int[N]; for(int i = 0; i < N; i ++) L[i] = input.nextInt(); input.close(); System.out.println(Solution(N, D, L)); } public static long Solution(int N, int D, int[] L) { final int MOD = 99997867; long sum = 0; int i = 0; int j = 2; while(j < N) { if(L[j] - L[i] > D) i ++; else if(j - i < 2) j ++; else { sum += Sum(j-i-1); j ++; } } return sum%MOD; } public static long Sum(long n) { return (1+n)*n/2; } }