Dirge_ level
腾讯_CSIG_后台开发工程师 identity
获赞
75
粉丝
2
关注
33
看过 TA
9
男
浙江大学
2020
C++
IP属地：广东
暂未填写个人简介
私信
关注
发布(3) 评论 刷题 收藏
2018-06-04 10:32
已编辑
腾讯_CSIG_后台开发工程师
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)
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客企业服务