首页 > 储物点的距离

Kur1su

发表于 2020-05-22 10:51:32

这题数据好多细节，气死本萌妹了 Description 一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间 ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点有个东西，要运到储物点，代价为就是储物点间的距离。 Solution 对于一个展开全文

19_hanhan

发表于 2020-05-16 22:02:52

题目题目描述：一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j ) dist就是储物点间的距离。&n 展开全文

一衍一

发表于 2020-05-14 12:04:10

题意:给定i和i+1两点的距离,i点的货物数量,以及费用计算方法ans=x * dist( i , j ),dist(i,j)为两点间距离然后每次查询将区间(i,j)的货物全部转移到x点所需要的费用ans题解:前缀和(1)求1点到i点的距离前缀和a[]区间[1,i]点货物集中到1点,1点货物总和的前展开全文

Canan

发表于 2020-05-14 15:19:30

https://ac.nowcoder.com/acm/problem/14683题意：大致意思就是把坐标轴一个区间里的所有数（权值）移动到某一点上，移动消耗为到目标点的距离*数字权值，计算总消耗。思路：0 <= ai,bi <= 2000000000，区间数据太大，枚举显然会TLE，展开全文

shyyhs

发表于 2021-01-10 16:55:05

算法: 前缀和,开始以为要离散化一下,写到一半发现不用. 思路: 就是按着题意给的意思模拟这个过程就好了.取模的时候别偷懒,会wa的. 代码: #include <bits/stdc++.h> using namespace std; typedef long long ll; cons 展开全文

sunrise__sunrise

发表于 2020-05-15 12:23:45

解题思路前缀和，千万千万注意减法取模……我半个多小时。。区间问题，居然要全部转移那么最简单模拟的话，出题人变态一点，每个区间都是最左端和最右端。时间复杂度毫无疑问爆炸了这时候，昨天的直播课，雨巨小姐姐刚好又说到了区间问题的解决办法！！吹爆。每个步骤都去模拟太蠢了，想想能不能用前缀和代替一下。区间问展开全文

ThinkofBlank

发表于 2020-05-14 14:51:55

这道题其实就是一道化式子的题，化完式子后就可以乱搞了/x 我们设pos[i]表示i号点的位置，特别的，pos[1]=0,那么，我们就可以根据i到i+1的距离，分别算出每个点的位置了。那么，我们就开始化式子吧。我们假设将i号点的物品搬到j号点去，那么代价就是：那么，如果将l-r号点的物品搬到展开全文

WuliWuliiii

发表于 2020-05-14 21:00:41

我采取了分别考虑的方式来解该问题，也就是将x和l、r的位置进行考虑了进去。于是，我定义了如下几个数组，分别表示： pre[x]包括x的前面的所有的货物都运送到x所需的花费suff[x]包括x的后面的所有的货都运送到x所需的花费ans[x]所有点的货物都运送到x所需的花费dis[x]表示x点到1 展开全文

与人无语

发表于 2020-05-22 08:44:32

这是一道前缀和的问题a[i]表示距离的前缀和 s[i]表示物品移动到1的价值的前缀和 b[i]表示物品数量的前缀和在对于l-r移动到x 有三种情况x<=l: 先全部移到1 对于每个储存点多移动了a[x]的距离即 ans=s[r]-s[l-1]-(b[r]-b[l-1])a[x]x> 展开全文

QingYa

发表于 2020-05-14 22:31:01

题意：一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j ) 展开全文

查看本题

查看本题讨论

等你来战

查看全部

牛客周赛 Round 93

报名截止时间：2025-05-18 21:00
衡阳师范学院第二十五届程序设计竞赛（同步赛）

报名截止时间：2025-06-08 18:00
2025牛客暑期多校训练营1

报名截止时间：2025-07-15 17:00

相关比赛

等你来战