补充

CSDN 阅读体验更佳：【训练题35：数学】D：石子游戏 | 2021牛客寒假算法基础集训营 5

【题意】D：石子游戏 | 2021牛客寒假算法基础集训营 5

• 一排，有 个石头堆，第 堆有 个石头。
  给你一个 。
  你每次可以选择相邻的 个石头堆，进行一次操作，这 堆，每堆石头个数都会**增加**
  问你最少操作个数使得每堆石头个数都相同，或者输出 表示不可能。

  【范围】

• 样例组数
  
  

  【思路】赛内

• 我感觉不是直接二分+贪心就能做好的，因为假设最后每堆石头个数都是
  可能 是可以达成的，但是 与 都是无法达成的，比较棘手。
  于是我就对 进行了分析：
  例子：
  我们已经假设最终每堆都有 个石头了，那么由于第一堆增加到 的方案只有一种，就是选择增加 堆，每堆增加 个，于是变成了：重复下去。第二堆石头需要增加 个，增加方案也只有一种，就是 堆每堆增加 个。
  我们从头到尾来一遍：可以看到，有解的情况就是 ，即**剩下下标从 的所有数字都相同。**
  当然还有一些特殊情况，比如：这样我们操作完之后，。这个时候，我们的解就是原来序列的元素的最大值。
  我们得到了 之后，就能知道增加了多少个石头，然后每次操作是增加 个，做个除法就行。
• 那么问题来了，我们代码里面怎么去设自变量 ?
  额，随便给一个大的常量就行了。 给小常量是不行的，因为这样比如可能导致上面例子中的 ，然后差分增加数字会比较麻烦。
• 我怎么知道当前位置为 还是某个数字增加了一些值后的新值？
  可以看到，一定是每 个数字一起变成 的，我们记录一下 表示第一位非 的位置即可。

  【代码】

• 时间复杂度： 记得用差分处理区间增加

  _            __   __          _          _
  | |           \ \ / /         | |        (_)
  | |__  _   _   \ V /__ _ _ __ | |     ___ _
  | '_ \| | | |   \ // _` | '_ \| |    / _ \ |
  | |_) | |_| |   | | (_| | | | | |___|  __/ |
  |_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
  const int MAX = 1e5+50;
  ll aa[MAX];
  ll de[MAX];
  ll aim = (ll)2e9;
  int main()
  {
    int T;scanf("%d",&T);
    while(T--){
        ll mx = 0;
        int n,k;scanf("%d%d",&n,&k);
        for(int i = 0;i <= n + 1;++i)de[i] = 0;
        for(int i = 1;i <= n;++i){
            scanf("%lld",&aa[i]);
            mx = max(mx,aa[i]);
        }
        bool can = true;
        ll now = 0;
        int last = 0;
        for(int i = 1;i + k - 1 <= n;++i){        // 算前面的区间都要变成 aim
            now += de[i];
            ll shu = aa[i] + now;
            if(shu > aim){
                can = false;
                break;
            }else if(shu < aim){
                de[i+1] += aim - shu;
                de[i+k] -= aim - shu;
                if(i > last)
                    last = i + k - 1;
            }
        }
        ll ans = -1;
        if(last){
            for(int i = n - k + 2;i <= last;++i){        // 这些数字必须都是 aim
                now += de[i];
                ll shu = aa[i] + now;
                if(shu != aim){
                    can = false;
                    break;
                }
            }
            for(int i = last + 1;i <= n;++i){            // 这些都是常数，常数都要相同
                now += de[i];
                ll shu = aa[i] + now;
                if(ans == -1)ans = shu;
                else if(ans != shu){
                    can = false;
                    break;
                }
            }
        }
        if(!can)puts("-1");
        else {
            if(ans == -1)ans = mx;
            ll cha = 0;
            for(int i = 1;i <= n;++i){
                cha += ans - aa[i];
            }
            cha /= k;
            printf("%lld\n",cha);
        }
    }
    return 0;
  }