初見安~這裡是兩個傳送門：洛谷P3620 & bzoj P1150
題目描述
你在一家 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 = 2 km。這種配對方案需要總長 4km 的網絡電纜，滿足距離之和最小的要求。
輸入格式
輸入檔案的第一行包含整數 n 和 k，其中 n(1≤n≤100 000)表示辦公樓的數目，k(1≤k≤n/2)表示可利用的網絡電纜的數目。
接下來的 n 行每行僅包含一個整數(0≤s≤1000 000 000), 表示每個辦公樓到大街起點處的距離。這些整數将按照從小到大的順序依次出現。
輸出格式
輸出檔案應當由一個正整數組成，給出将 2K 個相異的辦公樓連成 K 對所需的網絡電纜的最小總長度。
輸入
5 2
1
3
4
6
12
輸出
4
說明/提示
30%的輸入資料滿足 n≤20。
60%的輸入資料滿足 n≤10 000
題解
貪心果然是個博 大 精 深的算法呢。【大霧
題意很簡單——用K條邊從n個點裡面兩兩連接配接，并保證每個點最多被一條邊連接配接。讓K條邊的總長度最短。
可以可到的一個很明顯的貪心政策是每次都連接配接相鄰的兩個點【如果是題目本身就要求了的話感覺這一點題目沒有描述的很清楚……】，這樣的話我們一共就隻有n-1條邊供選擇。再來，轉化題意為：有n-1個數字，相鄰的兩個不能同時選擇，求選擇K個數字并使其之和最小。
好像有一種可以用dp做的感覺……不管了這裡講貪心【大霧】我們考慮：每次肯定是取最小的那個可以選的點。那麼最小的那個點左右還有兩個點，就要麼選左右兩個要麼隻選最小的那個。【左右兩個一定要同時選，因為如果隻選一個的話還不如選最小值呢，貪心就沒意義了。】是以我們幹脆把這三個綁在一起算——假設這三個值為
，那麼我們先假設選擇
。如果
更優怎麼辦呢？給自己留一個替換的機會咯——把這三個值取出來的同時放進去一個
，這樣的話再次選擇就意味着不選
了而是
。這樣一來我們操作K次取出最小值即可。
維護最小值可以寫一個小根堆，對于連續的三個的維護可以寫一個雙向連結清單。
提一個小細節——就是如果取出來的是
或者是
這種邊緣情況呢？很簡單，就如上面說到的“兩邊的值隻選一個還不如選中間那個最小的”的情況，把
和
指派為極大值，保證不會被選出來用于替換的那種即可，因為一定不會有替換的需求。
上代碼——
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100005
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
struct list {
int left, right, num;
}lst[maxn];
int n, K;
struct node {
int point;
node() {}
node(int nn) {point = nn;}
bool operator < (const node &x) const {return lst[x.point].num < lst[point].num;}
};
priority_queue<node> q;
bool vis[maxn];//标記哪些指針的點的最小值已經沒用了
ll ans = 0;
signed main() {
n = read(), K = read();
for(int i = 1; i <= n; i++) lst[i].num = read();
for(int i = n; i > 1; i--) lst[i].num -= lst[i - 1].num;//記得要從後往前求中間值
for(int i = 2; i <= n; i++) lst[i].left = i - 1, lst[i].right = i + 1;
for(int i = 2; i <= n; i++) q.push(node(i));//node隻有一個值……便于排序罷了。
lst[1].right = 2, lst[n + 1].left = n; lst[n + 1].num = lst[1].num = 0x3f3f3f3f;
//初始化
for(int i = 1; i <= K; i++) {
while(vis[q.top().point]) q.pop();//彈出不能用的點
int p = q.top().point;
q.pop();
ans += lst[p].num;
register int pre = lst[p].left, nxt = lst[p].right;
vis[pre] = vis[nxt] = true;//标記
lst[lst[pre].left].right = p;//維護雙向連結清單指針
lst[p].left = lst[pre].left;
lst[lst[nxt].right].left = p;
lst[p].right = lst[nxt].right;
pre = lst[pre].num, nxt = lst[nxt].num;//這裡就偷個懶而已
lst[p].num = pre + nxt - lst[p].num;//更新指針p的值，直接把D_{p-1}+D_{p+1}-D_p的值放進p位置
q.push(node(p));
}
printf("%lld\n", ans);
return 0;
}
整體代碼比較容易，但是思維複雜度……很有意思。
迎評：）
——End——