补充

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;
    }