2010-1092

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by 猛犸也钻地

解题报告：
{{{
先预处理，把数据读入，排好序，将线段加入优先队列。

每次从队列中取出长度最小的线段，将答案加上这段长度，然后将此线段与边上紧挨的两个线段合并，形成新线段。
新线段的长度为两边线段长度之和-自身长度，将它加入优先队列。

这意味着如果不选它，而选选择边上的线段，肯定是边上两个都选。
证明：在这三个线段之中，如果只选一个，必然是中间那个最好，因为它最短，而且对其他线段的选取不会造成干扰。如果选两个，显然只能选边上两个。

具体处理时，寻找边上的线段是个关键，可以采用类似链表的方式解决。关于这部分操作看下面代码会更容易理解。
}}}


代码：
{{{
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const long long INF = 1000000000000000000ll;

long long a[100001];
int l[100001],r[100001];

class Node{
public:
    int pos;
    Node(int t):pos(t){}
    bool operator <(const Node& rhs) const{
        return a[pos]>a[rhs.pos];
    }
};

int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)>0){
        long long ans=0;
        priority_queue<Node> q;
        a[0]=-INF;a[n+1]=INF;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a,a+n+2);
        for(int i=0;i<=n;i++){
            l[i]=i-1;r[i]=i+1;
            a[i]=a[i+1]-a[i];
            q.push(i);
        }
        while(k && !q.empty()){
            int p=q.top().pos;
            q.pop();
            if(r[p]<0) continue;
            k--;
            ans+=a[p];
            int x=l[p],y=r[p];
            a[p]=a[x]+a[y]-a[p];
            r[l[p]=l[x]]=l[r[p]=r[y]]=p;
            r[x]=r[y]=-1;
            q.push(p);
        }
        printf("%lld\n",ans);
    }
    return 0;
}
}}}

by 猛犸也钻地

解题报告：

先预处理，把数据读入，排好序，将线段加入优先队列。
每次从队列中取出长度最小的线段，将答案加上这段长度，然后将此线段与边上紧挨的两个线段合并，形成新线段。
新线段的长度为两边线段长度之和-自身长度，将它加入优先队列。
这意味着如果不选它，而选选择边上的线段，肯定是边上两个都选。
证明：在这三个线段之中，如果只选一个，必然是中间那个最好，因为它最短，而且对其他线段的选取不会造成干扰。如果选两个，显然只能选边上两个。
具体处理时，寻找边上的线段是个关键，可以采用类似链表的方式解决。关于这部分操作看下面代码会更容易理解。

代码：

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1000000000000000000ll;
long long a[100001];
int l[100001],r[100001];
class Node{
public:
    int pos;
    Node(int t):pos(t){}
    bool operator <(const Node& rhs) const{
        return a[pos]>a[rhs.pos];
    }
};
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)>0){
        long long ans=0;
        priority_queue<Node> q;
        a[0]=-INF;a[n+1]=INF;
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a,a+n+2);
        for(int i=0;i<=n;i++){
            l[i]=i-1;r[i]=i+1;
            a[i]=a[i+1]-a[i];
            q.push(i);
        }
        while(k && !q.empty()){
            int p=q.top().pos;
            q.pop();
            if(r[p]<0) continue;
            k--;
            ans+=a[p];
            int x=l[p],y=r[p];
            a[p]=a[x]+a[y]-a[p];
            r[l[p]=l[x]]=l[r[p]=r[y]]=p;
            r[x]=r[y]=-1;
            q.push(p);
        }
        printf("%lld\n",ans);
    }
    return 0;
}