codeforces 484 B Maximum Value (暴力乱搞)

2016年3月31日 0 作者 CrazyKK

题意:给出n个元素的序列,求出最大的a[i]%a[j] (i>=j)

Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (suchx divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM)



Sort the array and just maintain another array A of 10^6 elements where index i stores element just smaller than i

For example consider sorted array [2,4,7,11], then

A(0 indexed) will be [-1,-1,-1,2,2,4,4,4,7,7,7,7,11...]

-1 means no element is smaller than i.