上海市计算机学会12月丙组圆环选址计划

个人的思考方式或许并非最佳方案

1.首先设定一个终点（例如设定为1点），需计算从左侧至1点各节点的物资总量，以及从右侧至1点的物资总量，并统计整体花费

2.依次尝试每一个节点，假设从1移动至2，则原先位于1右侧的所有距离需增加1，而左侧的距离减少1。因此总花费应减去左侧物资总量，加上右侧物资总量，并计入距离为1的1点物资。在完成上述调整后（若节点数为奇数，则最远距离点会额外计算一次；若为偶数，则会额外计算两次），需要扣除多余计算的物资数量

3.随后更新左右区间内的物资总量

仅需遍历n个节点即可，时间复杂度为O(n)

关键数据类型应使用long long

 #include <iostream>

    
 using namespace std;
    
 const int N = 500010;
    
 typedef long long LL;
    
 LL q[