bzoj1150 [CTSC2007]資料備份Backup

​​http://www.elijahqi.win/archives/3131​​​

Description

　　你在一家 IT 公司為大型寫字樓或辦公樓（offices）的計算機資料做備份。然而資料備份的工作是枯燥乏味

的，是以你想設計一個系統讓不同的辦公樓彼此之間互相備份，而你則坐在家中盡享計算機遊戲的樂趣。已知辦公

樓都位于同一條街上。你決定給這些辦公樓配對（兩個一組）。每一對辦公樓可以通過在這兩個建築物之間鋪設網

絡電纜使得它們可以互相備份。然而，網絡電纜的費用很高。當地電信公司僅能為你提供 K 條網絡電纜，這意味

着你僅能為 K 對辦公樓（或總計2K個辦公樓）安排備份。任一個辦公樓都屬于唯一的配對組（換句話說，這 2K

個辦公樓一定是相異的）。此外，電信公司需按網絡電纜的長度（公裡數）收費。因而，你需要選擇這 K 對辦公

樓使得電纜的總長度盡可能短。換句話說，你需要選擇這 K 對辦公樓，使得每一對辦公樓之間的距離之和（總距

離）盡可能小。下面給出一個示例，假定你有 5 個客戶，其辦公樓都在一條街上，如下圖所示。這 5 個辦公樓分

别位于距離大街起點 1km, 3km, 4km, 6km 和 12km 處。電信公司僅為你提供 K=2 條電纜。

　　上例中最好的配對方案是将第 1 個和第 2 個辦公樓相連，第 3 個和第 4 個辦公樓相連。這樣可按要求使用

K=2 條電纜。第 1 條電纜的長度是 3km-1km=2km ，第 2 條電纜的長度是 6km-4km=2km。這種配對方案需要總長

4km 的網絡電纜，滿足距離之和最小的要求。

Input

第一行包含整數n和k

其中n（2≤n≤100000）表示辦公樓的數目，k（1≤k≤n/2）表示可利用的網絡電纜的數目。

接下來的n行每行僅包含一個整數（0≤s≤1000000000）,表示每個辦公樓到大街起點處的距離。

這些整數将按照從小到大的順序依次出現。

Output

輸出應由一個正整數組成，給出将2K個相異的辦公樓連成k對所需的網絡電纜的最小總長度。

Sample Input

5 2

1

3

4

6

12

Sample Output

4

HINT

Source

題意：給定n個數 要求k個不相鄰的最小值

做法：考慮目前一段是a,b,c那麼假如取走b就是将b的答案加入最後的答案然後将邊捆綁起來 變成a+c-b

#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fi first
#define se second
#define pa pair<int,int>
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int N=100100;
const int inf=0x3f3f3f3f;
int pre[N],nxt[N],n,k,len[N],ans;
priority_queue<pa,vector<pa>,greater<pa> >q;
int main(){
    freopen("bzoj1150.in","r",stdin);
    n=read();k=read();int x=read(),y;
    for (int i=1;i<n;++i) len[i]=(y=read())-x,x=y,pre[i]=i-1,nxt[i]=i+1;
    pre[1]=0;nxt[--n]=0;
    for (int i=1;i<=n;++i) q.push(make_pair(len[i],i));
    for (int i=1;i<=k;++i){static int x,l,r;
        while(q.top().first!=len[q.top().second]) q.pop();
        x=q.top().second;q.pop();l=pre[x];r=nxt[x];
        ans+=len[x];pre[x]=pre[l];nxt[x]=nxt[r];nxt[pre[l]]=pre[nxt[r]]=x;
        if (!l||!r) len[x]=inf;else len[x]=len[l]+len[r]-len[x]>=inf?inf:len[l]+len[r]-len[x];
        len[l]=len[r]=inf;q.push(make_pair(len[x],x));
    }printf("%d\n",ans);
    return 0;
}