Submission #67854576

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  /////////////////// 前入力 ///////////////////
  
  int q;
  cin >> q;

  /////////////////// 前処理 ///////////////////



  /////////////////// ループ ///////////////////

  // 問題数だけループ
  for (int loop=0; loop<q; loop++) {
    
    //////////////////// 入力 ////////////////////

    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i=0; i<n; i++) {
      cin >> a.at(i);
    }

    //////////////// 出力変数定義 ////////////////

    long long result = 0;

    //////////////////// 処理 ////////////////////

    // 長さが1になるまでループ
    while (a.size()>1) {

      // 前から順に、確認済みのやつを入れておくvector
      vector<long long> b;

      // 全部を後ろからチェックする
      while (!a.empty()) {

        long long num = a.back();
        a.pop_back();

        // これが最後の1つだった場合
        if (a.empty()) {

          // bの末尾がそれ以上ならそこに合体させる、小さければスルー、空でもスルー
          if (!b.empty()&&num<=b.back()) {
            result += b.back()-num;
            b.back()++;
          } else {
            b.emplace_back(num);
          }

        // これが最初の1つだった場合 
        } else if (b.empty()) {

          // aの末尾がそれ以上ならそこに合体させる、小さければスルー、空でもスルー
          if (!a.empty()&&num<=a.back()) {
            result += a.back()-num;
            a.back()++;
          } else {
            b.emplace_back(num);
          }

        // num<=a<bの場合
        } else if (num<=a.back()&&a.back()<b.back()) {

          // aに合流させる
          result += a.back()-num;
          a.back()++;

        // num<=b<aの場合
        } else if (num<=b.back()&&b.back()<a.back()) {

          // bに合流させる
          result += b.back()-num;
          b.back()++;

        // num<b==aの場合
        } else if (num<b.back()&&b.back()==a.back()) {

          // とりあえず同じ値に増やしておく
          result += a.back()-num;
          b.emplace_back(a.back());

        // いずれでもない場合
        } else {

          // スルー
          b.push_back(num);

        }

      }

      // 確認済のを全部戻す
      swap(a,b);
    }

    //////////////////// 出力 ////////////////////

    cout << result << endl;
    
  }

  /////////////////// 後処理 ///////////////////



  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result