BZOJ1150: [CTSC2007]数据备份Backup

输入的第一行包含整数n和k，其中n（2 ≤ n ≤100 000）表示办公楼的数目，k（1≤ k≤ n/2）表示可利用的网络电缆的数目。接下来的n行每行仅包含一个整数（0≤ s ≤1000 000 000）, 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出应由一个正整数组成，给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

5 2
1
3
4
6
12

4

上面的样例输入给出了前面描述的示例情形对于每一个测试点，如果写到输出文件中的答案正确，则得到该测试点100%的分数，否则得零分。30%的输入数据满足n≤20。60%的输入数据满足n≤10 000。

题解：

原来这题是CTSC的原题啊，我说为什么zxr的那场比赛有那么多人能想到标算，orz。

题解戳以前的链接http://www.cnblogs.com/zyfzyf/p/3988776.html

代码：

 1 #include<cstdio>
 2 
 3 #include<cstdlib>
 4 
 5 #include<cmath>
 6 
 7 #include<cstring>
 8 
 9 #include<algorithm>
10 
11 #include<iostream>
12 
13 #include<vector>
14 
15 #include<map>
16 
17 #include<set>
18 
19 #include<queue>
20 
21 #include<string>
22 
23 #define inf 1000000000
24 
25 #define maxn 100000+5
26 
27 #define maxm 500+100
28 
29 #define eps 1e-10
30 
31 #define ll long long
32 
33 #define pa pair<int,int>
34 
35 #define for0(i,n) for(int i=0;i<=(n);i++)
36 
37 #define for1(i,n) for(int i=1;i<=(n);i++)
38 
39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
40 
41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
42 
43 #define mod 1000000007
44 
45 using namespace std;
46 
47 inline int read()
48 
49 {
50 
51     int x=0,f=1;char ch=getchar();
52 
53     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
54 
55     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
56 
57     return x*f;
58 
59 }
60 int n,k,pre[maxn],nxt[maxn],len[maxn];
61 priority_queue<pa,vector<pa>,greater<pa> >q;
62 
63 int main()
64 
65 {
66 
67     freopen("input.txt","r",stdin);
68 
69     freopen("output.txt","w",stdout);
70 
71     n=read();k=read();int x=0,y;
72     for1(i,n)
73     {
74         y=read();
75         len[i]=y-x;x=y;pre[i]=i-1;nxt[i]=i+1;
76     }
77     pre[2]=0;nxt[n]=0;int ans=0;//只有n-1个距离才能计入权值
78     for2(i,2,n)q.push(pa(len[i],i));
79     for1(i,k)
80     {
81         while(len[q.top().second]!=q.top().first)q.pop();//已被删去的点
82         int c=q.top().second,l=pre[c],r=nxt[c];
83         ans+=len[c];q.pop();
84         pre[nxt[c]=nxt[r]]=nxt[pre[c]=pre[l]]=c;//删去c的前趋后继
85         len[c]=l&&r?min(inf,len[l]+len[r]-len[c]):inf;//加入一个新点，反悔点
86         len[l]=len[r]=inf;//删去点的权值记为inf，使它不会被堆弹出
87         q.push(pa(len[c],c));//加入
88     }
89     printf("%d\n",ans);
90 
91     return 0;
92 
93 }

View Code

BZOJ1150: [CTSC2007]数据备份Backup

1150: [CTSC2007]数据备份Backup

Description

Input

Output

Sample Input

Sample Output

HINT

Source

推荐阅读