BZOJ_1150_[CTSC 2007]データバックアップBackup_山+欲張り

BZOJ_1150_[CTSC 2007]データバックアップBackup_山+欲張り

Description

IT会社では、大規模なオフィスビルやオフィスビルのコンピュータデータをバックアップしています.しかし、データバックアップの作業は退屈です.
そのため、異なるオフィスビルを互いにバックアップするシステムを設計したいと思っていますが、家に座ってコンピュータゲームを楽しむことができます.既知のオフィス
ビルはみな同じ通りにある.あなたはこれらのオフィスビルにペアを組むことにしました(2つのグループ).各オフィスビルはこの2つの建物の間に網を敷くことができます.
ケーブルは互いにバックアップできるようにします.しかし、ネットワークケーブルの費用は高い.ローカルテレコムはK本のネットワークケーブルしか提供できません.これは
K対オフィスビル(または合計2 Kのオフィスビル)のバックアップのみを手配できます.いずれのオフィスビルも唯一のペアグループに属しています(言い換えれば、この2 K
このオフィスビルはきっと違うに違いない).また、電信会社はネットワークケーブルの長さ(キロ数)で料金を徴収する必要があります.だから、このK対オフィスを選ぶ必要があります.
ケーブルの全長をできるだけ短くします.言い換えれば、このK対のオフィスビルを選択して、各対のオフィスビル間の距離の和(総距離)を選択する必要があります.
できるだけ小さくする.次の例では、5人のお客様がオフィスビルが1つの街にあると仮定します.下図に示します.この5つのオフィスビルは
大通りの起点から1 km、3 km、4 km、6 km、12 kmに位置しない.電信会社はK=2本のケーブルしか提供していません.
上記の例では、1番目と2番目のオフィスビルを接続し、3番目と4番目のオフィスビルを接続するのがベストです.必要に応じて使用できます
K=2本のケーブル.1本目のケーブルの長さは3 km-1 km=2 km、2本目のケーブルの長さは6 km-4 km=2 kmです.このペアリングスキームには総長が必要だ
4 kmのネットワークケーブルは、距離の和の最小の要件を満たしています.

Input

最初の行は整数nとkを含む
ここで、n(2≦n≦100000)はオフィスビルの数を表し、k(1≦k≦n/2)は利用可能なネットワークケーブルの数を表す.
次のn行は、各オフィスビルから通りの起点までの距離を示す整数(0≦s≦10000000)のみを含む.
これらの整数は、小さい順に表示されます.

Output

出力は、2 K個の異なるオフィスビルをk対に接続するために必要なネットワークケーブルの最小総長を与える正の整数で構成されるべきである.

Sample Input

5 2 1 3 4 6 12

Sample Output

4
木のような問題https://www.cnblogs.com/suika/p/9062716.html
距離の差を分けると、K個を選んで互いに隣接しないようにし、総和を最小限に抑えることに相当します.
植樹と違って今回はリングではなく、毎回1つ選ぶ保証はありません.
そこで新しいポイント重み値をinfに設定すればよい.
 
コード:

#include 
#include 
#include 
#include 
using namespace std;
using namespace __gnu_pbds;
#define N 100050
typedef long long ll;
int n,K,b[N],L[N],R[N],vis[N];
ll a[N];
struct node {
    int x;
    bool operator a[y.x];
    }
};
__gnu_pbds::priority_queueq;
void del(int x) {
    L[R[x]]=L[x]; R[L[x]]=R[x]; vis[x]=1;
}
int main() {
    scanf("%d%d",&n,&K);
    int i;
    for(i=1;i<=n;i++) {
        scanf("%d",&b[i]);
    }
    ll ans=0;
    for(i=1;i

 
転載先:https://www.cnblogs.com/suika/p/9127296.html