[bzoj] 1150: [CTSC2007]数据备份Backup

发表于   |   分类于   |  

题意

　　n个点在一条直线上的不同位置,选出k个点对,使得点对间的距离和最小.要求每个点最多属于一个点对.

传送门

分析

贪心,但是显然每次选当前可选线段中的最短线段是不对的.
我们要考虑到把选择的线段”放回去”的过程.

  • 当我们选择一条线段时,与这条线段相邻的两条线段显然不能再选.
  • 当我们要放回一条线段时,只有当它两侧的线段同时被选.

当我们选择一条线段时,我们可以删除相邻的两条线断并添加一个新的元素:它的权值赋为左右两端线段权值之和减去当前线段权值.

这时当我们选择一个元素时就放弃了原来的线段而选择了它两侧的线段,线段数目加了一但是总权值增加了.
这样我们就可以用堆来实现了.

当然也可以用一些技巧用优先队列实现.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <queue>

struct NODE {
trueint w , p , t ;
truebool operator < (const NODE& b) const { return w < b.w ; }
} ;

#define  maxn  100010LL
#define  infi  2000000000LL

int n , k ;
std::priority_queue<NODE>h ;
int a[maxn] ;
int pre[maxn] , back[maxn] , t[maxn] ;
/*链表*/
bool v[maxn] = {0} ;

int main() {
int i , ans , pos , left , right ;
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) , read(k) ;
trueRep (i,1,n) read(a[i]) ;
trueRev (i,n,2) a[i] -= a[i-1] ;
truea[1] = a[++n] = infi ;
trueRep (i,1,n) {
truetrueh.push((NODE){-a[i],i,1}) ;/*大根堆所以-a[i]*/
truetruepre[i] = i-1 , back[i] = i+1 , t[i] = 1 ;
true}
trueans = 0 ;
trueNODE x ;
truewhile (k --> 0) {
truetruefor (x=h.top() ; v[x.p]||x.t!=t[x.p] ; h.pop(),x=h.top()) ;
truetrueans -= x.w ;/*更新答案*/
truetruepos = x.p ;
truetrueleft = pre[pos] , right = back[pos] ;
truetrueback[left] = back[right] ; pre[back[right]] = left ;
truetruev[pos] = v[right] = true ;
truetruea[left] += a[right]-a[pos] ;
truetrueh.push((NODE){-a[left],left,++t[left]}) ;
true}
trueprintf("%d\n", ans) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章