codeforces 484 B Maximum Value (暴力乱搞)

题目链接
题意:给出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)

题解也没有特别懂。。。感觉和筛法有点类似。

不过学到了一个o(1)时间得到小于x的最大数是多少的做法。

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.

见代码中的b数组。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz