「BZOJ1150」[CTSC2007] 数据备份Backup

2014年5月7日7,7750

Description

Input

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

Output

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

Sample Input

5 2
1
3
4
6
12

Sample Output

HINT

上面的样例输入给出了前面描述的示例情形

对于每一个测试点，如果写到输出文件中的答案正确，则得到该测试点100%的分数，否则得零分。30%的输入数据满足n≤20。60%的输入数据满足n≤10 000。

题解

此题同2288

首先一定取的每一段都连接着相邻的楼

我们可以每次取最小的一段用堆维护

但是这样发现过不了样例，因为一栋楼只能被连接一次

考虑样例

转化为2 1 2 6中取俩个但不能相邻

在取1的时候可以加入2+2-1=3

以后取3表示不取1取两边

边界同样要考虑

比如1 2 3 4

取完1以后加入1显然是有问题的

我们其实可以直接舍弃2，可以证明无论在什么情况下，取2一定没有取1优

取2后能取的其它数取1后也能取

于是在2288的基础上随便改改就行了

快速读入飞速233

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define inf 0x7fffffff
using namespace std;
struct heap{int v,x;}h[200010];
int n,m,a[100010];
int tmp,sz,ans,tot;
int v[100010],cnt;
int next[100010],pre[100010],pos[100010];
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
void pushup(int x)
{
    while(h[x].v<h[x>>1].v)
    {
        pos[h[x>>1].x]=x;
        swap(h[x],h[x>>1]);
        x=x>>1;
    }
    pos[h[x].x]=x;
}
void push(int v,int x)
{
    sz++;h[sz].v=v;h[sz].x=x;
    pos[x]=sz;
    pushup(sz);
}
void pushdown(int x)
{
    int to;
    while((x<<1)<=sz)
    {
        to=(x<<1);
        if(to<sz&&h[to].v>h[to+1].v)to++;
        if(h[x].v>h[to].v)
        {
            pos[h[to].x]=x;
            swap(h[to],h[x]);
            x=to;
        }
        else break;  
    }
    pos[h[x].x]=x;
}
void del(int x)
{
    h[x].v=inf;
    pushdown(x);
}
void init()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=2;i<=n;i++)
    {
	    push(a[i]-a[i-1],i);
	    pre[i]=i-1;next[i]=i+1;
	}
	pre[2]=next[n]=-1;
}
void solve()
{
	int a,b;
    heap k;
    for(int i=1;i<=m;i++)
    {
    	 k=h[1];
         if(pre[k.x]==-1)
         {
             ans+=k.v;
             del(1);del(pos[next[k.x]]);
             pre[next[next[k.x]]]=-1;
         }
         else if(next[k.x]==-1)
         {
             ans+=k.v;
             del(1);del(pos[pre[k.x]]);
             next[pre[pre[k.x]]]=-1;
         }
         else
         {
             ans+=k.v;
             a=next[k.x];b=pre[k.x];
             pre[k.x]=pre[b];next[pre[b]]=k.x;
             next[k.x]=next[a];pre[next[a]]=k.x;
             h[1].v=h[pos[a]].v+h[pos[b]].v-h[1].v;
             pushdown(1);
             del(pos[a]);del(pos[b]);
         }
    }
    printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#define inf 0x7fffffff

using namespace std;

struct heap{int v,x;}h[200010];

int n,m,a[100010];

int tmp,sz,ans,tot;

int v[100010],cnt;

int next[100010],pre[100010],pos[100010];

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

void pushup(int x)

{

while(h[x].v<h[x>>1].v)

{

pos[h[x>>1].x]=x;

swap(h[x],h[x>>1]);

x=x>>1;

}

pos[h[x].x]=x;

}

void push(int v,int x)

{

sz++;h[sz].v=v;h[sz].x=x;

pos[x]=sz;

pushup(sz);

}

void pushdown(int x)

{

int to;

while((x<<1)<=sz)

{

to=(x<<1);

if(to<sz&&h[to].v>h[to+1].v)to++;

if(h[x].v>h[to].v)

{

pos[h[to].x]=x;

swap(h[to],h[x]);

x=to;

}

else break;

}

pos[h[x].x]=x;

}

void del(int x)

{

h[x].v=inf;

pushdown(x);

}

void init()

{

n=read();m=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=2;i<=n;i++)

{

push(a[i]-a[i-1],i);

pre[i]=i-1;next[i]=i+1;

}

pre[2]=next[n]=-1;

}

void solve()

{

int a,b;

heap k;

for(int i=1;i<=m;i++)

{

k=h[1];

if(pre[k.x]==-1)

{

ans+=k.v;

del(1);del(pos[next[k.x]]);

pre[next[next[k.x]]]=-1;

}

else if(next[k.x]==-1)

{

ans+=k.v;

del(1);del(pos[pre[k.x]]);

next[pre[pre[k.x]]]=-1;

}

else

{

ans+=k.v;

a=next[k.x];b=pre[k.x];

pre[k.x]=pre[b];next[pre[b]]=k.x;

next[k.x]=next[a];pre[next[a]]=k.x;

h[1].v=h[pos[a]].v+h[pos[b]].v-h[1].v;

pushdown(1);

del(pos[a]);del(pos[b]);

}

printf("%d\n",ans);

}

int main()

{

init();

solve();

return 0;

}

« 「BZOJ2288」「POJ Challenge」生日礼物「BZOJ2697」特技飞行 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1150」[CTSC2007] 数据备份Backup

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论