【数学】D:石子游戏 | 2021牛客寒假算法基础集训营 5

石子游戏

https://ac.nowcoder.com/acm/contest/9985/D

补充

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;
    }
全部评论

相关推荐

10-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
vegetable_more_exercise:1-1.5万,没错啊,最少是1人民币,在区间内
点赞 评论 收藏
分享
秋招进行到现在终于能写总结了。完全没想到战线会拉这么长,过程会如此狼狈,不过更应该怪自己太菜了。好在所有的运气都用在了最后,也是有个去处。背景:双2本硕科班,无竞赛,本科一段研究所实习,硕士一段大厂暑期实习但无转正。技术栈是C++&nbsp;&amp;&nbsp;Golang,实习是客户端音视频(而且是鸿蒙端开发),简历两个C++项目一个Golang项目。主要投递岗位:后端,cpp软开,游戏服务端,测开,以及一些不拘泥于Java的岗位。从8月起总共投递123家公司,笔试数不清了,约面大约30家。offer/oc/意向:友塔游戏(第一个offer,面试体验很好,就是给钱好少南瑞继保(计算机科班点击就送(限男生),不...
乡土丁真真:佬很厉害,羡慕~虽然我还没有到校招的时候,也想讲一下自己的看法:我觉得不是CPP的问题,佬的背书双2,技术栈加了GO,有两段实习。投了123,面了30.拿到11个offer。这个数据已经很耀眼了。这不也是CPP带来的吗?当然也不止是CPP。至少来说在这个方向努力过的也会有好的结果和选择。同等学历和项目选java就会有更好的吗?我个人持疑问态度。当然CPP在方向选择上确实让人头大,但是我觉得能上岸,至于最后做什么方向,在我看来并不重要。至于CPP特殊,有岗位方向的随机性,java不是不挑方向,只是没得选而已。也希望自己以后校招的时候能offer满满
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务