浮游大陆的68号岛

公主殿下MIKU · 2018-10-20 18:43:26 · 题解

第一次发题解。

此题暴力肯定不行，需要用前缀和和后缀和来优化。

用sum1[i]表示将从1号仓库到i-1号仓库的物品全转移到i号仓库的代价；

dis1[i]表示从1号仓库到i号仓库的距离；

tot1[i]表示从1号仓库到i号仓库的全部物品的个数；

sum2[i]表示将从n号仓库到i+1号仓库的物品全转移到i号仓库的代价；

dis2[i]表示从n号仓库到i号仓库的距离；

tot2[i]表示从n号仓库到i号仓库的全部物品的个数.

l r与x的关系有三种情况:

①如果x在r右边，将l r移动到x需要从前向后运（前缀和）则有： (suml[r]-suml[l])将1到 l从l移动到 r， -totl[l-1](disl[r]-disl[l])减去将1到l-1从l移动到r， +(totl[r]-totl[l-1])(dis1[x]-disl[r])加上将l到r从r移动到x；

②如果x在l左边，将l r移动到x需从后向前运（后缀和）则有： (sum2[l]-sum2[r])将n到 r从r移动到 l， -tot2[r+1](dis2[l]-dis2[r])减去将n到r+1从r移动到l， +(tot2[l]-tot2[r+1])(dis2[x]-dis2[l])加上将r到l从l移动到x；

③如果x在l和r中间，l到x从前向后运（前缀和），r到x从后向前运(后缀和)： sum1[x]-sum1[l-1] 将1到l从l移动到x， +sum2[x]-sum2[r+1]将n到r从r移动到x， -tot1[l-1](dis1[x]-dis1[l-1])减去将 1到l从l移动到x， –tot2[r+1](dis2[x]-dis2[r+1])减去将n到r从r移动到x。

同时,还要注意不断取模，不要到最后再模，以防爆long long。

代码的话，就自己写吧。