Hello those who are reading my entry, I have a small problem that i'm kinder curious about my solution. ↵
↵
***The problem is:↵
↵
You have an array of integers (a[i]<=1e6) sized of n (n<=1e3). You have to split the array m different segment which cover the whole array. An action will take 1 unit of time which let you do 1 of those 2 at a time (each take 1 unit of time):↵
↵
- You can minus 1 from a[i] ↵
↵
- You can plus 1 from a[i]↵
↵
Your task is to mange to split the segments somehow that all of the value in 1 segment need to be the same by using those action i mention. And also those segment action work separately, which mean the answer would be the maximum action of 1 of those m segments.↵
↵
Test Case:↵
↵
Input:↵
↵
6 2↵
↵
1 1 2 3 4 3↵
↵
Output: ↵
↵
1↵
↵
Explain: 2 segments are 1 1 2 and 3 4 3, you can turn it into 1 1 1 and 3 3 3***↵
↵
My idea:↵
↵
Due to the fact that actions need for a subarray is going to be larger if it contains more value (or the subarray is larger) because the action we have to use is abs(a[i]-median) so base on the linear spec, we could use greedy to put as many as we could into a segment so that their action won't exceed the answer (cause we only focus about the max value). ↵
↵
I would use binary search to search for the answer, for each mid I search, I would check it for each segment as I mention to make sure that none of them could exceed by using 2 pointer L and R. For each L, I will find all the median in (L, R) and check to make sure the actions follow the rule by extend the R pointer to the furthest position (rightest what I mean). ↵
↵
And if everything is ok, then just print the answer. However, the time limit could be O(n^2*LogN^2), which mean 20*20*1000*1000 or 400 million calculations, may exceed 1 second limit. Forgot to mention, I use Persistent Data Structures to find the (r-l+1)/2 smallest value to find the median.↵
↵
time limit: 1s↵
↵
memory limit: 256mb↵
↵
***The problem is:↵
↵
You have an array of integers (a[i]<=1e6) sized of n (n<=1e3). You have to split the array m different segment which cover the whole array. An action will take 1 unit of time which let you do 1 of those 2 at a time (each take 1 unit of time):↵
↵
- You can minus 1 from a[i] ↵
↵
- You can plus 1 from a[i]↵
↵
Your task is to mange to split the segments somehow that all of the value in 1 segment need to be the same by using those action i mention. And also those segment action work separately, which mean the answer would be the maximum action of 1 of those m segments.↵
↵
Test Case:↵
↵
Input:↵
↵
6 2↵
↵
1 1 2 3 4 3↵
↵
Output: ↵
↵
1↵
↵
Explain: 2 segments are 1 1 2 and 3 4 3, you can turn it into 1 1 1 and 3 3 3***↵
↵
My idea:↵
↵
Due to the fact that actions need for a subarray is going to be larger if it contains more value (or the subarray is larger) because the action we have to use is abs(a[i]-median) so base on the linear spec, we could use greedy to put as many as we could into a segment so that their action won't exceed the answer (cause we only focus about the max value). ↵
↵
I would use binary search to search for the answer, for each mid I search, I would check it for each segment as I mention to make sure that none of them could exceed by using 2 pointer L and R. For each L, I will find all the median in (L, R) and check to make sure the actions follow the rule by extend the R pointer to the furthest position (rightest what I mean). ↵
↵
And if everything is ok, then just print the answer. However, the time limit could be O(n^2*LogN^2), which mean 20*20*1000*1000 or 400 million calculations, may exceed 1 second limit. Forgot to mention, I use Persistent Data Structures to find the (r-l+1)/2 smallest value to find the median.↵
↵
time limit: 1s↵
↵
memory limit: 256mb↵
