一道并查集题,”=”写成”==”到能过30个样例然后又糊了两个钟
题目链接
题意:
给出n,代表n天
一条鲨鱼第i能移动的距离是$a_i$
求一个最小的k
当鲨鱼那天移动的距离小于k,停在当前位置;大于等于k,离开
(不回头)
并且这k要使停留在每个地方的天数相等
(口糊,还是请看原题描述)
大致思路:
arr数组:题目给出的移动距离
升序sort一遍,然后枚举arr[1]+1到arr[n]+1
枚举到i时,就会把未sort前的arr分割成多个集合
(分割是因为当前枚举的值,比之前的大)
集合代表着一次停留
多少个集合就是停留多少次
集合的大小就是这一次停留了多少天
检查一下每个集合的大小是否相同,相同就更新答案
把每个元素连在一起就用并查集
代码:
1 |
|