Aizu Online Judge 2104 - Country Road

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2104

日本語.

解法

戸の家を1個の発電機でカバーすることを考えると電線は左端の家から右端の家までの線分1本となり, この長さが最小の料金に対応します. 発電機が2個あれば, 隣り合う家間の距離のうちどれか1つを使わずに済ませることができます. このとき最も長いものを使わずに済ませるのが最適です.同様にして発電機が個ある場合のことを考えると, 隣り合う家間のすべての線分の長さのうち大きい方から本無効にすることによって解を得ることができます.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> cost;
vector<int> xi;

int main() {
    int t, n, k;
    cin >> t;

    while (t--) {
        cin >> n >> k;

        xi = vector<int>(n);
        cost = vector<int>(n - 1);

        for (int i = 0; i < n; i++) {
            cin >> xi[i];
            if (i > 0) cost[i - 1] = xi[i] - xi[i - 1];
        }
        sort(cost.begin(), cost.end(), greater<int>());

        int ans = 0;
        for (int i = k - 1; i < cost.size(); i++) {
            ans += cost[i];
        }
        cout << ans << endl;
    }

    return 0;
}

感想

気づけば簡単ですね. 気づくのにものすごい時間がかかりましたが...