| Day7-例3 |
| 难度级别：C； 运行时间限制：5000ms； 运行空间限制：256000KB； 代码长度限制：2000000B |
|
试题描述
|
|
|
|
输入
|
|
输入的第一行包含整数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
|
题解：奇妙的题。用堆维护每一段，如果取了一个就要把（两边的-这个）放到堆里，表示可以改成选两边的，但是就是不能同时选。
用set实现：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+;
const long long inf=4e18;
struct data{long long v;int p;};
bool operator<(const data&a,const data&b){return a.v<b.v||(a.v==b.v&&a.p<b.p);}
inline long long read(){
long long x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
set<data>S;
long long A[maxn],d[maxn];
int L[maxn],R[maxn],n,k;
int main(){
data x;set<data>::iterator t;
n=read();k=read();
for(int i=;i<=n;i++)A[i]=read();
for(int i=;i<n;i++)d[i]=A[i+]-A[i];d[]=inf;d[n]=inf;
for(int i=;i<n;i++)R[i]=i+,L[i+]=i;
for(int i=;i<=n;i++)S.insert((data){d[i],i});
long long ans=;
for(int i=;i<=k;i++){
t=S.begin();x=*t;ans+=x.v;
int l=L[x.p],r=R[x.p];
S.erase(t);S.erase((data){d[l],l});S.erase((data){d[r],r});
R[l]=R[r];L[R[r]]=l;d[l]+=d[r]-x.v;
S.insert((data){d[l],l});
}write(ans);return ;
}
treap仍然调不对啊。。。为什么。。。我改了重载也过不了啊。。。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<ctime>
#include<set>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define CH for(int d=0;d<2;d++)if(ch[d])
using namespace std;
const int maxn=+,maxnode=+;
const long long inf=4e18;
struct data{long long v;int p;};
bool operator>(const data&a,const data&b){return a.v>b.v||(a.v==b.v&&a.p>b.p);}
bool operator==(const data&a,const data&b){return (a.v==b.v)&&(a.p==b.p);}
struct node{
node*ch[];data v;int siz,r;
void init(){siz=;r=rand();ch[]=ch[]=NULL;return;}
void update(){siz=;CH{siz+=ch[d]->siz;}return;}
}treap[maxnode],*nodecnt=treap,*root;queue<node*>RM;
node*newnode(){node*k;if(RM.empty())k=nodecnt++;else k=RM.front(),RM.pop();k->init();return k;}
void del(node*&x){RM.push(x);x=NULL;return;}
void rotate(node*&x,int d){
node*k=x->ch[d^];x->ch[d^]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;
}
void insert(node*&x,data v){
if(!x)x=newnode(),x->v=v;
else{int d=v>x->v;insert(x->ch[d],v);
if(x->r<x->ch[d]->r)rotate(x,d^);else x->update();
}return;
}
void remove(node*&x,data v){
if(x->v==v){
if(x->ch[]&&x->ch[]){
int d=x->ch[]->r>x->ch[]->r;rotate(x,d);remove(x->ch[d],v);
}else{node*k=x;x=x->ch[]?x->ch[]:x->ch[];del(k);}
}else remove(x->ch[v>x->v],v);
if(x)x->update();return;
}
void print(node*x){
if(!x)return;print(x->ch[]);printf("%lld ",x->v.v);print(x->ch[]);return;
}
data getmi(node*x){
if(x->ch[])x=x->ch[];return x->v;
}
inline long long read(){
long long x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
long long A[maxn],d[maxn];
int L[maxn],R[maxn],n,k;
int main(){
srand(time());
n=read();k=read();
for(int i=;i<=n;i++)A[i]=read();
for(int i=;i<n;i++)d[i]=A[i+]-A[i];d[]=inf;d[n]=inf;
for(int i=;i<n;i++)R[i]=i+,L[i+]=i;
for(int i=;i<=n;i++)insert(root,(data){d[i],i});
long long ans=;
for(int i=;i<=k;i++){
data t=getmi(root);ans+=t.v;
int l=L[t.p],r=R[t.p];
remove(root,t);remove(root,(data){d[l],l});remove(root,(data){d[r],r});
R[l]=R[r];L[R[r]]=l;d[l]+=d[r]-t.v;
insert(root,(data){d[l],l});
}write(ans);return ;
}