AOJ2104 Country Road

問題

Country Road | Aizu Online Judge

限界集落には一直線上の道があり、電気の通らない家々が立ち並ぶ。

個の家が数直線状に並び、個の発電機が与えられる。全ての家に発電機から出る電気を行き渡らせたい。 発電機から出る電気は家同士を電線で結ぶことで、共有することが出来る。しかし電線を引くには長さに比例するだけのコストがかかる。引くべき電線の長さの最小値を求めよ。

• 
• 
• 

解答

発電機が1つの場合、全ての道を覆う必要がある。 発電機が1つ増えると、覆う区間が2つに分割される。の区間がどこかの区間を覆う必要がなくなる。覆う必要がない区間のうち、最大のものを覆わないのが最も効率が良い。これを繰り返す。 よって、全体を覆う長さから個の発電機を使って、覆わない区間を貪欲に選んで引いていけばよい。

int main() {

  int T; cin >> T;
  while(T--) {
    int N, K; cin >> N >> K;
    vector<int> a(N);
    rep(i, N) {
      cin >> a[i];
    }
    ll asum = 0;
    sort(a.begin(), a.end());
    rep(i, N - 1) {
      asum += a[i + 1] - a[i];
    }
    priority_queue<ll, vector<ll>> pq;
    rep(i, N - 1) {
      pq.push(a[i+1] - a[i]);
    }

    ll msum = 0;
    rep(i, N - 1) {
      if(K > 1) {
        K--;
        msum += pq.top();
        pq.pop();
      }
    }

    cout << asum - msum << endl;
  }
  
  return 0;
}