[HOJ 396] Rabbit Rush

作法：

原題的敘述我看蠻久才看懂的......其實他要問的是「將原數列分成 k 陀，使得 sigma( 一坨內按某種順序取相鄰數的差的總和 ) 最小」，而可以看出其實那個值就等於一坨內的最大值減最小值，所以如果一坨內有 x 和 y ，那麼把 x , y 中間的數全部加進來不會更差，所以可以先把原數列排序，這 k 陀就對應到 k 條線段，並且他們兩兩不相交，復蓋了這 n 個點。如果把要求的東西用「原數列的最大值減最小值」扣掉，就會剩下 k-1 條連接相鄰點的線段，而我們要讓這些線段的長度總和最大，所以就取前 k-1 大的就好了。而因為要拔點，所以還要維護這些差值的資料結構，我自己是用 linked list 詢問每個要刪掉的點的左右是誰，還有用兩個 multiset 分別放目前取的前 k-1 大的差值和剩下的差值。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
map<int,int> mp ;
int a[maxn] ;
int nex[maxn],las[maxn],head,tail ;
int maxl,sum ;
 
multiset<int,greater<int> > st1 ;
multiset<int> st2 ;
 
void erase2(int val)
{
    auto it=st1.find(val) ;
    if(it!=st1.end()) st1.erase(it) ;
    else
    {
        st2.erase(st2.find(val)) ;
        sum-=val ;
        st2.insert(*st1.begin()) ;
        sum+=*st1.begin() ;
        st1.erase(st1.begin()) ;
    }
}
 
void insert(int val)
{
    st2.insert(val) ; sum+=val ;
    st1.insert(*st2.begin()) ; sum-=*st2.begin() ;
    st2.erase(st2.begin()) ;
}
 
void erase(int x)
{
    int id=mp[x] ;
    if(id==tail || id==head)
    {
        int val ;
        if(id==tail) val=a[id]-a[las[id]] , tail=las[id] ;
        else val=a[nex[id]]-a[id] , head=nex[id] ;
        maxl=a[tail]-a[head] ;
        erase2(val) ;
    }
    else
    {
        int val1=a[id]-a[las[id]] , val2=a[nex[id]]-a[id] ;
        las[nex[id]]=las[id] , nex[las[id]]=nex[id] ;
 
        insert(val1+val2) ;
        erase2(val1) ; erase2(val2) ;
    }
}
 
main()
{
    int n,k,Q ; scanf("%d%d%d",&n,&k,&Q) ;
    k-- ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]) ;
        nex[i]=i+1 ; las[i]=i-1 ;
    }
    head=1 ; tail=n ;
    sort(a+1,a+n+1) ;
    maxl=a[n]-a[1] ;
    for(int i=1;i<=n;i++)
    {
        mp[a[i]]=i ;
        if(i<n) st1.insert(a[i+1]-a[i]) ;
    }
 
    sum=0 ;
    for(int i=1;i<=k;i++)
    {
        sum+=*st1.begin() ;
        st2.insert(*st1.begin()) ;
        st1.erase(st1.begin()) ;
    }
    printf("%d\n",maxl-sum) ;
 
    while(Q--)
    {
        int x ; scanf("%d",&x) ;
        erase(x) ;
        printf("%d\n",maxl-sum) ;
    }
}