Floating range of stock price
Time limit: up to 30 use cases, 1 second (C/C + +), 1.5 seconds (Java) / memory limit: 256 MB (Stack 1 MB)
It is assumed that the stock price of a company over an N-day period will be provided. You occasionally use the past stock price for simulation investment, but the violent fluctuation of stock price will make you feel uneasy, so you want to know when the stock price remains almost unchanged. The price here is almost constant, which means that the difference between the maximum value and the minimum value of the stock over a period of time is less than the given K value.
For example, given the stock price in the past 10 days and K=10 as above, it can be explained that the price has hardly changed in the other 9 days except the last day when the stock price is 15. (the maximum value in the first 9 days is 13 and the minimum value is 3, and the difference between the two is 10, which satisfies K=10. However, on the 10th day, the stock price is 15, and the difference from the minimum value 3 is 12, which exceeds K=10.) In addition, 9 days is the longest duration of almost no change in stock price.
Write a program to calculate the maximum duration when the difference between the maximum and minimum stock values is less than or equal to K during a given period.
[restrictions]
1. The number of days N is an integer between 1 and 300000.
2. The stock price is an integer between 1 and 1000000000.
3. The difference K between the minimum value and the maximum value is an integer between 1 and 1000000000.
[input]
The first line gives the number of test cases T. Then T test cases are given. The space in the first line of each test case gives the total number of days N and K. The space in the next line is distinguished, and the stock price of N days is given in order of time from far to near.
[output]
The answers of each test case are output according to the sequence standard. For each case, output "#x" (x is the test case number, starting from 1), add a space (excluding quotation marks), and output the maximum duration (days) required to meet the conditions in the topic.
[input / output example]
(input)
3
10 10
17 25 22 15 18 18 21 12 5 25
10 10
8 11 3 10 11 7 7 13 10 15
1 1
1000000000
(output)
#1 7
#2 9
#3 1
Solution:
1. Find the maximum and minimum values of the interval, that is, the extreme value of the interval. When using Indexed Tree, you need to declare two trees
2. The interval is variable. Double pointers can be considered. For this problem, the left and right of the interval are moving, but the moving speed is different. The fast and slow pointers can be used
3. If the number of days n < 300000, hashing is not required
package tree;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* Solution:
* 1.Find the maximum and minimum values of the interval, that is, the extreme value of the interval. Use the Indexed Tree to declare two trees
* 2.The interval is variable. Double pointers can be considered. For this problem, the left and right sides of the interval are moving, but the moving speed is different. The fast and slow pointers can be used
* If the number of days n < 300000, hashing is not required
*
* @author XA-GDD
*
*/
public class EQ_BoxPattern_0705 {
static int T,N,K;
static int _Max_N = 300000;
static int [] srcArr = new int[_Max_N+2];
static int [] minIdxTree = new int[(_Max_N)*4]; //Interval minimum tree
static int [] maxIdxTree = new int[(_Max_N)*4]; //Interval maximum tree
static int offset;
static int ans;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("D:\\workspace\\eclipse-workspace\\sw_pro\\test_case\\sample_input_0705.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int testCase = 1; testCase<=T;testCase++) {
init();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
//Initialize tree
int k=0;
while((1<<k)<N) {
k++;
}
offset=1<<k;
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) { //Each time a value is read, the maximum and minimum values of the interval are updated
update(offset+i,Integer.parseInt(st.nextToken()));
}
getLongestTime();
System.out.println("#"+testCase+" "+ans);
}
}
static void getLongestTime() {
int fast = 0; //Quick pointer
int slow = 0; //Slow pointer
for(int i=0;i<N;i++) {
fast = i;
int difVal = query(offset+slow,offset+fast);
while(difVal>K) { //If the difference exceeds the range of K, the pointer moves slowly
slow++;
difVal = query(offset+slow,offset+fast);
}
ans = Math.max(ans, fast-slow+1);
}
}
//Update maximum and minimum values
static void update(int index ,int val) {
minIdxTree[index] = val;
maxIdxTree[index] = val;
index= index>>1;
while(index>0) {
minIdxTree[index] = Math.min(minIdxTree[index*2], minIdxTree[index*2+1]);
maxIdxTree[index] = Math.max(maxIdxTree[index*2], maxIdxTree[index*2+1]);
index = index>>1;
}
}
//Query the difference between the maximum and minimum values
static int query(int start ,int end) {
int minRes = Integer.MAX_VALUE;
int maxRes = Integer.MIN_VALUE;
while(start<=end) {
if(start%2==1) {
minRes = Math.min(minRes, minIdxTree[start]);
maxRes = Math.max(maxRes, maxIdxTree[start]);
}
if(end%2==0) {
minRes = Math.min(minRes, minIdxTree[end]);
maxRes = Math.max(maxRes, maxIdxTree[end]);
}
start = (start+1)>>1;
end = (end-1)>>1;
}
return maxRes-minRes;
}
static void init() {
ans=0;
Arrays.fill(srcArr,0);
Arrays.fill(minIdxTree, Integer.MAX_VALUE);
Arrays.fill(maxIdxTree, Integer.MIN_VALUE);
}
}