結果

問題 No.738 平らな農地
ユーザー しらっ亭
提出日時 2017-05-30 03:43:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,133 bytes
コンパイル時間 1,850 ms
コンパイル使用メモリ 170,956 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-10-13 13:41:13
合計ジャッジ時間 5,734 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 10 TLE * 1 -- * 76
権限があれば一括ダウンロードができます

ソースコード

diff # 

// O(N K log K)

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

int64_t solve(const int n, const int k, const vector<int> &A) {
  int64_t ans = 1e18;
  int l = (k + 1) / 2;

  // n 回ループ
  for (int i = 0; i < n; i++) {
    if (i >= k - 1) {
      // priority_queue を使って中央値を求める
      // O(k log k)
      // O(k) で中央値を求める方法も存在するが、割愛
      priority_queue<int> pq;
      for (int j = 0; j < k; j++) {
        pq.emplace(A[i-j]);
        if ((int) pq.size() > l) {
          // 大きい値を捨てる
          pq.pop();
        }
      }
      int median = pq.top();

      // 中央値との差の和を全て足す
      // O(k)
      int64_t cand = 0;
      for (int j = 0; j < k; j++) {
        cand += abs(median - A[i-j]);
      }

      //cout << i << ": (" << median << ", " << cand << ")" << endl;
      ans = min(ans, cand);
    }
  }

  return ans;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, k; cin >> n >> k;
  vector<int> A(n);
  for (int i = 0; i < n; i++) cin >> A[i];

  cout << solve(n, k, A) << endl;

  return 0;
}
0