首页 > MooFest
开通博客写题解
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-03 19:27:37
MooFest 题目大意 分析 其实我们发现这个十分不好维护 就是说，如果已经保证了，那么原式可以写为 这个按照从大到小就可以了吧 那么就是的问题了 这个看看数据，这个大概是需要一个的复杂度 那么发现像什么线段树，树状数组之类的高级数据结构就可以维护 就分成两种情况，一种是的，一种是的 那就分别求和 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Dear㉿You
发表于 2020-09-03 09:24:32
前言(划重点) 1.题目要求n*(n-1)/2对，即不能重复2.答案是 max(v[i],v[j]) × dis(i,j) 的求和 解决方案 既然不能n方，那我们只好单独算出每头牛对于答案的贡献。所以可以按照v从小到大排序，这样可以直接通过求出这头牛与之前的牛的总距离求出答案。 总距离想一 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 zxjyes
发表于 2020-09-02 14:11:07
其实，我英语水平垃圾的很。。。题目大意：给你坐标和每个坐标的权值，题目求n个坐标两两之间的“声音权值”的和，其中任意两个点之间的“声音权值” = 距离*max(两点的权值）。1.暴力求解法：容易想，也容易TLE2.树状数组：我们在处理的过程中，按照权值大小升序排序，可以省略掉取max的步骤。对于排序 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shyyhs
发表于 2020-09-02 00:11:53
考验你对于树状数组单点修改区间查询的理解... for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { ans+=abs(a[i].x-a[j].x)*max(a[i].v,a[j].v 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”