The following is a programming problem of byte jumping on the network. I wrote a solution with a time complexity of O(n*n), but it timed out. Later, I saw an algorithm with a time complexity of O(n). I called it to explore the algorithm to the right.

Time limit: 1 second for C / C + + and 2 seconds for other languages

Space limit: C/C++ 128M, other languages 256M

My name is Wang Dashi. I'm an agent. I have just received a task: ambush in the street of byte jump to catch the terrorist Kong lianshun. I'm working with two other agents, and I suggest

- We chose three ambush sites out of N buildings in bytechop street.
- In order to take care of each other, we decided that the distance between the two agents farthest away should not exceed D.

I'm a genius! After careful calculation, we chose one of the X feasible ambush schemes. This plan is foolproof, tremble, Kong lianshun!

......

Unexpectedly, the plan failed. Kong lianshun disguised as a little dragon girl and escaped from the street of byte jump in cosplay's team. It's just that his disguise is too successful. Even when Yang Guo comes, he can't find it!

Listen to the question: given N (the number of buildings that can be used as the ambush point), D (the maximum distance between the two agents farthest away) and the coordinates of the optional buildings, calculate how many ambush options the sledgehammer team has in this operation.

Be careful:

- Two agents can't ambush in the same place
- The three agents are equivalent: that is, the same location combination (A, B, C) is only an ambush method and cannot be reused because of "agents exchange positions"

Enter a description:

The first line contains two numbers, N and D, separated by spaces (1 n n ; 1000000; 1 D 1000000)

The second line contains the positions of N buildings, each of which is represented by an integer (value range is [0, 1000000]), arranged from small to large (byte jumping street is regarded as a number axis)

Output Description:

A number indicating the number of different ambush schemes. The result may overflow. Please take the mold for 99997867

Input example 1:

4 3

1 2 3 4

Output example 1:

4

Example 1:

Options (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

Input example 2:

5 19

1 10 20 30 50

Output example 2:

1

Example 2:

Options (1, 10, 20)

Own code:

import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); List<Integer> list = new ArrayList<Integer>(); for(int i = 0;i<n;i++) { list.add(sc.nextInt()); } Main e2 = new Main(); int ans = e2.solution(n,m,list); System.out.println(ans); } public int solution(int n,int m,List<Integer> list) { int ans = 0; int temp = 2; if(n<2) return 0; for(int i = 0;i<n-2;i++) { for(int j = temp;j<n;j++) { if((list.get(j)-list.get(i))<=m) { ans = ans + (j-i-1); } } temp++; } return ans%99997867; } }

Code idea: two iterations, the left side (head) of the traversal value of the outer side and the right side (tail) of the traversal value of the inner layer.

Correct code:

import java.util.Scanner; public class Exercie02_Answer { private int mod = 99997867; private void sln() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(), D = sc.nextInt(); long cnt = 0; if (N <= 2) { System.out.println(-1); return; } int[] locs = new int[N]; for (int i = 0; i < N; i++) { locs[i] = sc.nextInt(); } sc.close(); int left = 0, right = 2; while (right < N) { if (locs[right] - locs[left] > D) left++; else if (right - left < 2) right++; else { cnt += calC(right - left); right++; } } cnt %= mod; System.out.println(cnt); } private long calC(long num) { return num * (num - 1) / 2; } public static void main(String[] args) { new Exercie02_Answer().sln(); } }

Code idea: one time traversal starts from subscript 2 and right traverses the tail of the value. If possible, fix the right end of the value and select two numbers from the front. Since the right side is fixed, the three values will not be repeated.

Q: why not repeat?

A: fix the value on the right, that is, let Wang Dashi stand on the right every time, and let the other two people take two values from the beginning of the left to the front of the tail. It's easy to know through the idea of arrangement and combination that all values may not be repeated; if the right is shifted to the right, the value of the tail bar after the right is shifted will not be repeated with any value different from that of his tail. " In a word, as long as the right side is fixed, the value will not be repeated.

The key to the right search algorithm: fix the traversal variables (the number of traversals is the tail of the whole possible value), and select other values from the left.