AOJ/vol21/2104 - Wiki2D

AOJ - 2104 : Country Road (カントリーロード)

問題概要

日本語文があるので省略。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104

解法

貪欲に解けます。

始め、家がある位置全てに発電所があると仮定します。
もし、kがn以上であるならば、このとき答えは0になります。

次に、kがn-1であるならば、現在n個ある発電所の内、1つだけなくさなくてはいけないということがわかります。
なくすという表現をしていますが、最も隣同士の距離が近い発電所同士を併合してやればいいだけです。
あとは、この処理を(n-k)回行えばいいです。

プログラム

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n, k;
int t[100002];
 
int main(){
  int T;
  cin >> T;
 
  while(T--){
    vector<int> vec;
 
    cin >> n >> k;
    k = min(k, n); //kは、nよりでかくなくていい
 
    for(int i = 0; i < n; i++){
      cin >> t[i];
      if(i != 0) vec.push_back(t[i] - t[i - 1]); //隣の家との距離をpush_back
    }
 
    //家同士の距離を昇順にソート
    sort(vec.begin(), vec.end());
 
    int ans = 0;
    for(int i = 0; i < n - k; i++){
      ans += vec[i];
    }
    cout << ans << endl;
  }
}