首页 > Bunny的聚会
开通博客写题解
头像 偶尔刷刷题
发表于 2019-08-25 11:59:16
题目大意：数轴上有n个点，在总代价不超过m的情况下，至多可以将多少个点移到一起？（代价：每个点移动的距离） 数据范围500万，递增输入，不需要排序，显然需要用O(n)做法才能满分，而且读入还可能被卡。 能走到一起的，必然是连续的若干个点：如果一个区间中有个点没有移动过去，那么终点要么在他左边，要么在 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 wzliwzli
发表于 2019-08-26 14:39:25
10%的数据显然可以直接爆搜，爆搜每一步让哪一只兔子往哪里走。 复杂度O((2n)k)O((2n)^k)O((2n)k)。 20%的数据这里保证兔子的位置单调递增，显然最终的答案是把一段连续区间里的兔子全部聚在一起，那么我们可以枚举这段区间的左右端点，枚举把兔子聚集到的位置，判断是否能让这段区间内的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”