Bytedance AI Camp 6.2在线编程第二题

题意大致如下:
有n个实数的数组a[],求   两两之差的绝对值向下取整   的   和.
第一行输入n,m
第二行n个长整形b[],实数a[i] = b[i]/m
0 < n < 1e5, 0 < m < 1e9, 0< b[i] < 1e18.

3 3
1 3  6
则 1/3, 1, 2
两两之差为2/3, 5/3, 1
向下取整为0, 1, 1
答案为2.
#笔试题目##字节跳动#
全部评论
我说下O(NlogN)的做法. 先按照b[i]排序 考虑b[I]=k[I]*m+r[I] , 其中0<=r[I]<m 答案 其中对于固定的i,可以利用后缀和计算; 因此关键在于求 事实上,对于每对,我们考虑:如果,那么;否则. 因此还是对于固定的i,我们需要计算有多少个j,满足:j>i 且。这一步可以用离散化+树状数组解决。 最后的时间复杂度是O(NlogN+N*(1+1+logN))=O(NlogN)
点赞 回复 分享
发布于 2018-06-04 03:49
我连15分都没有。。。只有5分。。。第一题也是,是不是python都跑不出来,得用c++或者java呀
点赞 回复 分享
发布于 2018-06-02 23:35
这题我只会处理整数的,就是前15分。整数的情况很容易找到递推关系,复杂度O(N);小数的没想到好办法。
点赞 回复 分享
发布于 2018-06-02 18:02

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务