原题链接
Description
给出数轴上的n(n≤105)个点，要求从中选出k(k≤n/2)对点，使得每对点之间的距离之和最小。点的坐标范围为[0,109]。
Solution
感觉挺巧妙的。容易知道每个点对必然是相邻的两个点，那么本题就相当于从n−1个数中选出k个互不相邻的数，使得其和最小。
这里就要用到一个思想，姑且叫做反悔思想。大意就是当我们进行操作a后，加入另一个操作a′，执行a′就可以抵消a带来的影响，或者说撤销a。
那么对于这道题来说，我们首先用链表来存储这n−1个数和它们的前驱后继。我们每次选出最小的数At，将At加入ans，然后同时删除At，At−1和At+1（因为选了At就不能选它们了）。然后我们加入一个数At−1+At+1−At，其前驱是At−2，后继是At+2。当我们选择这个数的时候，就相当于放弃选择At，而是选择At−1和At−2。
举个例子：7,9,8,6,4,2,3,8−→−−Del 27,9,8,6,5(4+3−2),8−→−−Del 57,9,8,9(6+8−5) 可以看到当我们选择合并后的5后，ans=7=2+(4+3−2)=4+3，{6,4,2,3,8}不可选，这就相当于选择了4,3这两个数。
因为我们每次都要取出最小的数，所以可以使用堆。
时间复杂度O(nlogn)。
Code
//[CTSC2007]数据备份Backup
#include <cstdio>
#include <queue>
inline char gc()
{static char now[1<<16],*S,*T;if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}return *S++;
}
inline int read()
{int x=0; char ch=gc();while(ch<'0'||'9'<ch) ch=gc();while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();return x;
}
int const N=1e5+10;
int const INF=0x3F3F3F3F;
int n,k; int d[N];
bool del[N];
struct rec
{int id,len,pre,nxt;bool operator<(const rec x) const{return len>x.len;};
}r[N];
std::priority_queue<rec> Q;
int main()
{n=read(),k=read();for(int i=1;i<=n;i++) d[i]=read();r[0].id=0,r[0].len=INF,r[0].pre=0,r[0].nxt=1; Q.push(r[0]);r[n].id=n,r[n].len=INF,r[n].pre=n-1,r[n].nxt=n; Q.push(r[n]);for(int i=1;i<=n-1;i++){r[i].id=i; r[i].len=d[i+1]-d[i];r[i].pre=i-1,r[i].nxt=i+1;Q.push(r[i]);}int ans=0;while(k){int t=Q.top().id; Q.pop();if(del[t]) continue;ans+=r[t].len;int t1=r[t].pre,t2=r[t].nxt;k--; del[t1]=del[t2]=true;r[t].len=r[t1].len+r[t2].len-r[t].len;r[r[t].pre=r[t1].pre].nxt=t; r[r[t].nxt=r[t2].nxt].pre=t;Q.push(r[t]);}printf("%d\n",ans);return 0;
}附上原60分网络流做法：
//[CTSC2007]数据备份Backup
#include <cstdio>
#include <cstring>
#include <queue>
inline char gc()
{static char now[1<<16],*S,*T;if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}return *S++;
}
inline int read()
{int x=0; char ch=gc();while(ch<'0'||'9'<ch) ch=gc();while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();return x;
}
int const N=1e5+10;
int const INF=0x3F3F3F3F;
int n,k,a[N];
int s,t,h[N],cnt;
struct edge{int v,c,w,nxt;} ed[N<<2];
void edAdd(int u,int v,int c,int w)
{cnt++; ed[cnt].v=v,ed[cnt].c=c,ed[cnt].w=w,ed[cnt].nxt=h[u],h[u]=cnt;cnt++; ed[cnt].v=u,ed[cnt].c=0,ed[cnt].w=-w,ed[cnt].nxt=h[v],h[v]=cnt;
}
int dst[N],pre[N];
std::queue<int> Q; bool in[N];
bool SPFA()
{memset(dst,0x3F,sizeof dst);Q.push(s),in[s]=true; dst[s]=0;while(!Q.empty()){int u=Q.front(); Q.pop(),in[u]=false;for(int i=h[u];i;i=ed[i].nxt){int v=ed[i].v,w=ed[i].w;if(ed[i].c&&dst[u]+w<dst[v]){dst[v]=dst[u]+w,pre[v]=i;if(!in[v]) Q.push(v),in[v]=true;}}}return dst[t]<INF;
}
int main()
{n=read(),k=read();for(int i=1;i<=n;i++) a[i]=read();s=0,t=n+2; cnt=1;for(int i=1;i<=n;i+=2){edAdd(s,i,1,0);if(i>1) edAdd(i,i-1,1,a[i]-a[i-1]);if(i<n) edAdd(i,i+1,1,a[i+1]-a[i]); }for(int i=2;i<=n;i+=2) edAdd(i,n+1,1,0);edAdd(n+1,t,k,0);int ans=0;while(SPFA()){for(int i=pre[t];i;i=pre[ed[i^1].v]) ed[i].c-=1,ed[i^1].c+=1;ans+=dst[t];}printf("%d\n",ans);return 0;
}P.S.
咕咕咕了这么久…咸死我了
没想到傅里叶变换那篇阅读量居然1.5k啦！╰(￣▽￣)╮
