Problem:5126 新建题解

Solution_ID:27215            题解

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<cstdio>

int a[100010],n,ans=0;

void qsort(int l,int r)

{

int i=l,j=r,mid=a[(l+r)/2],t;

while(i<=j)

{

while(a[i]<mid) i++;

while(mid<a[j]) j--;

if(i<=j)

{

t=a[i]; a[i]=a[j]; a[j]=t;

i++; j--;

}

}

if(l<j) qsort(l,j);

if(i<r) qsort(i,r);

}

int main()

{

scanf("%d",&n); int f[n];

for(int i=1;i<=n;i++) scanf("%d",&f[i]);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

qsort(1,n-1); 

ans=f[n]*2+a[n]; printf("%d\n",ans);

for(int i=n-1;i>=1;i--) { ans+=a[i]; printf("%d\n",ans); }

return 0;

}


by 50475 六月 9, 2017, 8:05 p.m.

Solution_ID:24820            熟悉优先队列的使用

                   时间复杂度:Θ() 空间复杂度:Θ()

我的博客原文:https://www.hexcode.cn/article/show/noip2015-salesman


通过这道题,可以很好的学习和练习使用C++STL库中queuepair的使用。
之前一直使用纯粹的C,有需要的地方就自己使用struct写链表等数据结构,因此排序、极值、哈希搜索等操作不仅写起来费事,而且效率不高,这一题彻底让我从之前纯粹使用C的方式转换成了使用C++和STL。
题目地址:<a href="http://codevs.cn/problem/5126/">http://codevs.cn/problem/5126/</a>
关于优先队列priority_queuepair,可以参考下面两篇比较全面的介绍:
<a href="http://www.cnblogs.com/flyoung2008/articles/2136485.html">优先队列priority_queue 详解</a>
<a href="http://blog.csdn.net/xywlpo/article/details/6458867">C++中pair的用法</a>
值得注意的是,pair不光做好了泛型,还做了operator<的实现,因此可以默认通过priority_queue进行最大堆的操作,而不需要自己写比较函数。

<h4><a></a>解题思路:</h4>

构建数据结构,distance距离位置,和value疲劳值。
将所有数据分为两个序列,左部lq和右部rq,分割点就在当前推销员所在的坐标位置(一开始坐标点在0点处),动态维护其坐标的变化。左部序列是一个大顶堆的优先队列,初始时为空;右部元素不必单独开辟,直接使用左边界哨兵控制区域位置即可。

<h5><a></a>每次对左部和右部的最大值进行对比:</h5>
  • 如果左部最大值大一些,则此时选择左部元素(推销员已走过的房间),将左部元素的value值输出,并弹出这个元素。
  • 如果右部最大值大一些,则此时选择右部元素(推销员还没到过的坐标),将右部元素的(distance - nowDis) * 2 + value值输出,同时记录目标元素的distance值,并将右部元素中所有小于等于此distance值的节点全部压入左部队列,压入权值为每个元素的value值。
<h5><a></a>寻找最大值的方法:</h5>
  • 左部元素寻找最大值的方法:直接使用优先队列的特性,lq的top元素。

  • 右部元素寻找最大值的方法:在rq中依次遍历,寻找最大的(distance - nowDis) * 2 + value

直到左部和右部序列全部为空,解题结束。

实际编码中,我并没有每次对比左部和右部的最大值,而是在开始时将右部元素全部整理压入左部队列,然后将左部队列依次输出即可。整理和压入的方法是:寻找到右部(distance - nowDis) * 2 + value最大值后,将目标元素以(distance - nowDis) * 2 + value权值入栈,其余distance小于等于目标元素distance的节点以value值入栈。这样程序显得简洁一点。

<h5><a></a>代码:</h5>
/**
  * NOIP2015 推销员
  * 学习使用pair泛型进行组合,而不需要自己写struct
  * 学习使用priority_queue优先队列(默认为最大堆)
  */
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4.in","r",stdin);
    //freopen("C:\\Users\\Administrator\\Desktop\\salesman\\salesman4-dd.out","w",stdout);
    int N;
    scanf("%d", &N);
    pair<int, int> nodes[N];
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].second);      //读入dis数据
    }
    for(int i = 0; i < N; i++){
        scanf("%d", &nodes[i].first);       //读入value数据
    }

    priority_queue< pair<int, int> > lq;    //左部优先队列

    int nowPos = 0, nowDis = 0, nowResult = 0, tempPos, tempMXPos, tempResult, tempMXResult;

    //将nowPos不断向N逼近,迫使右部数据全部进入左部队列,最后整体输出左部队列
    while(nowPos < N){
        //找到本次登记的最大result和最大dis
        tempMXResult = 0;
        for(tempPos = nowPos; tempPos < N; tempPos++){
            tempResult = (nodes[tempPos].second - nowDis) * 2 + nodes[tempPos].first;
            if( tempResult >= tempMXResult ){
                tempMXResult = tempResult;
                tempMXPos = tempPos;
            }
        }
        nowDis = nodes[tempMXPos].second;
        //tempMXPos的权值为tempMXResult,其余小于nowDis的右部元素权值为first,将这些元素全部压入优先队列lq中
        for(tempPos = nowPos; nodes[tempPos].second <= nowDis && tempPos < N; tempPos++){
            if(tempPos == tempMXPos){
                nodes[tempPos].first = tempMXResult;
            }
            lq.push(nodes[tempPos]);
        }
        nowPos = tempPos;
    }

    while(!lq.empty()){
        nowResult += lq.top().first;
        printf("%d\n", nowResult);
        lq.pop();
    }

    return 0;
}

by 36953 二月 5, 2017, 4:33 p.m.

Solution_ID:23490            不好意思

                   时间复杂度:Θ() 空间复杂度:Θ()

不好意思下面题解是优化过的,所以d数组其实是没用的


by 31151 十一月 16, 2016, 8:40 p.m.

Solution_ID:23489            终于没超时了

                   时间复杂度:Θ() 空间复杂度:Θ()

var n,o,p,t,max,r:longint;

a,b,c,d:array[1..1000000] of longint;

procedure qsort(l,r:longint);

var i,j,mid,w:longint;

begin

i:=l;j:=r;

mid:=c[(i+j)div 2];

repeat

while c[i]<mid do inc(i);

while c[j]>mid do dec(j);

if i<=j then begin w:=c[i];c[i]:=c[j];c[j]:=w;inc(i);dec(j); end;

until i>j;

if i<r then qsort(i,r);

if l<j then qsort(l,j);

end;

begin  max:=-999;

read(n);

for o:=1 to n do

read(a[o]);

for o:=1 to n do

read(b[o]);

for o:=1 to n do

if a[o]*2+b[o]>max then begin r:=o;max:=a[o]*2+b[o]; end;

d[1]:=max;

for o:=1 to n do

if a[o]>a[r] then c[o]:=a[o]*2+b[o]-2*a[r] else c[o]:=b[o];

c[r]:=max;

qsort(1,n); t:=0;

for o:=n downto 1 do

begin

t:=t+c[o];

writeln(t);

end;

end.


by 31151 十一月 16, 2016, 8:33 p.m.

Solution_ID:23290            用树状数组

                   时间复杂度:Θ(猜) 空间复杂度:Θ(猜)

想拿满分,需要优化选择下一个最优点的时间复杂度,有很多种方式(单调队列、堆、树状数组),这里我采用了树状数组维护区间最值的方法,建立两个树状数组,分别表示当前距离范围内的最大疲劳值、超过距离范围的(疲劳值+增加的往返距离值)最大值。

附上代码:

var 

 i,n,j,m,tmp,k1,k2,tot,maX1,maX2,tmp2:longint; 

 a,s,a2,s2,idX,idX2,idXid,idX2id,b:array[0..100000] of longint; 

function lowbit(X:longint):longint; 

begin 

eXit(X and (-X)); 

end

procedure update(i,X:longint); 

var j:longint; 

begin 

 j:=i; 

while i<=n do 

begin

if idX[i]<X then 

begin 

 idX[i]:=X; idXid[i]:=j; 

end

 inc(i,lowbit(i)); 

end

end

procedure update_desc(i,X:longint);//相当于逐个建立树状数组 

var j:longint; 

begin 

 j:=i; 

while i<=n do 

begin 

if idX2[i]<X then 

begin 

 idX2[i]:=X; idX2id[i]:=j; 

end;

 inc(i,lowbit(i)); 

end

end

procedure modify(p,n:longint); 

var i,j:longint; 

begin 

 i:=p;a[i]:=0

while i<=n do 

begin 

 idX[i]:=a[i];idXid[i]:=i; j:=1

while j<lowbit(i) do 

begin 

if idX[i]<idX[i-j] then 

begin

idX[i]:=idX[i-j]; idXid[i]:=idXid[i-j]; 

end

 j:=j shl 1

end

 inc(i,lowbit(i)); 

end

end;

function query(m:longint):longint; 

begin 

 query:=0

while m>0 do 

begin 

if query<idX[m] then 

begin 

 query:=idX[m]; k1:=idXid[m]; 

end

 dec(m,lowbit(m)); 

end

end;

function query2(m:longint):longint; 

begin 

 query2:=0

while m>0 do 

begin

if query2<idX2[m]-s[tmp]*2 then 

begin //tmp是上次选中的编号 

 query2:=idX2[m]-s[tmp]*2; k2:=idX2id[m]; 

end

 dec(m,lowbit(m)); 

end

end

begin 

 readln(n); 

for i:=1 to n do read(s[i]);

readln;//距离数组 

for i:=1 to n do read(a[i]);

readln;//疲劳值数组 

for i:=1 to n do s2[n+1-i]:=s[i]; 

for i:=1 to n do a2[n+1-i]:=a[i]; 

for i:=1 to n do update(i,a[i]); 

for i:=1 to n do update_desc(i,s2[i]*2+a2[i]); 

 tmp:=n+1

for i:=n downto 1 do //b[i]表示记录相同距离元素的最右边序号 

if s[tmp]<>s[i] then 

begin 

 b[i]:=i; tmp:=i; 

end 

else b[i]:=tmp; 

 j:=1;m:=0;tmp:=0

while j<=n do 

begin 

 maX1:=query(m);//前tmp个元素求最大值 

 maX2:=query2(n-m);//从tmp+1到n个元素中求算上距离的最大值 

if maX1>maX2 then 

begin

inc(tot,maX1); 

 tmp2:=k1; 

end 

else 

begin 

 inc(tot,maX2); 

 m:=b[n+1-k2]; 

 tmp:=n+1-k2; 

 tmp2:=n+1-k2; 

end

 writeln(tot); 

 modify(tmp2,n); 

 inc(j); 

end

end.


by 40319 十一月 12, 2016, 8:26 p.m.

Solution_ID:22717            给份简单的

                   时间复杂度:Θ() 空间复杂度:Θ()

include<cstdio>

#include<queue>

using namespace std;

const int N=100010;

struct node{

    int s,v;

    bool operator < (node a)const{ return v<a.v;}

}h[N],s;

priority_queue<node> q;

int n,x;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&h[i].s);

    for(int i=1;i<=n;i++)scanf("%d",&h[i].v);

    s.s=s.v=0;

    q.push(s);

    int now=0,mx=0;

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

        int next=now;

        s=q.top();

        mx=s.v;

        for(int j=now+1;j<=n;j++)//寻找now以后的最优房屋

            if(h[j].v+(h[j].s-h[now].s)*2>mx){

                mx=h[j].v+(h[j].s-h[now].s)*2;

                next=j;

            }

        h[next].v+=(h[next].s-h[now].s)*2;//更新

        if(now!=next)q.push(h[next]);//入队

        for(int j=now+1;j<next;j++)//now到next之间的房屋入队

        q.push(h[j]);

        s=q.top();//弹出堆顶

        x+=s.v;//加入答案

        q.pop();

        printf("%d\n",x);//输出

        now=next;//now=next继续寻找最优值

    }

    return 0;

}


by 36997 十月 29, 2016, 8:24 p.m.

Solution_ID:21861            下面的那个是错的,样例都过不了

                   时间复杂度:Θ(o(n log n)) 空间复杂度:Θ()

贪心

贪心思路不提,关键是如何判断左边和右边那个最大

建两个堆,一个维护左边的最大值,另一个维护右边的最大值

右边的再加上一些东西,去维护位置,取出右边最大值时,要把右边堆中小于该位置编号的点全部取出放入左边那个堆

用next来记录上个从右边堆取出的那个点的位置




var left,right,num,wei,a,tr,s,s1:array[0..100000]of longint;

    i,j,n,next,l1,sum,l2,t:longint;


procedure push1(x:longint);

var k:longint;

begin

if x=1 then exit;

if right[x]>right[x div 2] then

begin

k:=right[x];

right[x]:=right[x div 2];

right[x div 2]:=k;

wei[num[x]]:=x div 2;

wei[num[x div 2]]:=x;

k:=num[x];

num[x]:=num[x div 2];

num[x div 2]:=k;

k:=s[x];

s[x]:=s[x div 2];

s[x div 2]:=k;

push1(x div 2);

end;

end;


procedure down1(x:longint);

var k,w:longint;

begin

if l1<x*2 then exit;

w:=x*2;

if(x*2+1<=l1)and(right[w]<right[x*2+1]) then

w:=x*2+1;

if right[w]>right[x] then

begin

k:=right[w];

right[w]:=right[x];

right[x]:=right[w];

wei[num[x]]:=w;

wei[num[w]]:=x;

k:=num[x];

num[x]:=num[w];

num[w]:=k;

k:=s[x];

s[x]:=s[w];

s[w]:=k;

down1(w);

end;

end;


procedure push2(x:longint);

var k:longint;

begin

if x=1 then exit;

if left[x]>left[x div 2]

then

begin

k:=left[x];

left[x]:=left[x div 2];

left[x div 2]:=k;

push2(x div 2);

end;

end;


procedure down2(x:longint);

var k,w:longint;

begin

if l2<x*2 then exit;

w:=x*2;

if(x*2+1<=l2)and(left[w]<left[x*2+1]) then

w:=x*2+1;

if left[w]>left[x] then

begin

k:=left[w];

left[w]:=left[x];

left[x]:=k;

down2(w);

end;

end;


begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

begin

read(tr[i]);

s1[i]:=2*a[i]+tr[i];

wei[i]:=i;

end;

next:=0;

for i:=1 to n do

begin

num[i]:=i;

s[i]:=a[i];

right[i]:=s1[i];

wei[i]:=i;

push1(i);

end;

l1:=n;

l2:=0;

a[0]:=0;

sum:=0;

fillchar(left,sizeof(left),0);

repeat

if l1+l2=0 then break;

if left[1]<=right[1]-2*a[next] then

begin

sum:=sum+right[1]-2*a[next];

for i:=next+1 to num[1]-1 do

begin

inc(l2);

left[l2]:=tr[i];

push2(l2);

end;

t:=num[1];

for i:=next+1 to t do

begin

right[wei[i]]:=right[l1];

num[wei[i]]:=num[l1];

s[wei[i]]:=s[l1];

wei[num[l1]]:=wei[i];

right[l1]:=0;

dec(l1);

down1(wei[i]);

end;

next:=t;

end

else

begin

sum:=sum+left[1];

left[1]:=left[l2];

left[l2]:=0;

dec(l2);

down2(1);

end;

writeln(sum);

until false;

end.


by 17574 十月 4, 2016, 2:02 p.m.

Solution_ID:21659            记住我的大名——鲍张冰

                   时间复杂度:Θ(破冰) 空间复杂度:Θ(破冰)

var
    a,s:array[1..100000] of longint;
    n,sum,i,j,k:longint;
procedure temp(var x,y:longint);
var
    tmp:longint;
begin
    tmp:=x;x:=y;y:=tmp;
end;
procedure qsort(l,r:longint);
var
    i,j,mid,mid2:longint;
begin
    i:=l;j:=r;
    mid:=a[(l+r) div 2];
    repeat
    while (a[i]<mid) do inc(i);
    while (mid<a[j]) do dec(j);
    if i<=j then begin temp(a[i],a[j]);
    inc(i);
    dec(j);
    end;
    until i>j;
    if l<j then qsort(l,j);
    if i<r then qsort(i,r);
    end;
begin

    readln(n);
    for i:=1 to n do read(s[i]);
    readln;
    for i:=1 to n do read(a[i]);
    readln;
    qsort(1,n-1);
    sum:=s[n]*2+a[n];
    writeln(sum);
    for i:=n-1 downto 1 do
    begin
    sum:=sum+a[i];
    writeln(sum);
    end;
end.

by 18968 九月 26, 2016, 8:29 p.m.

Solution_ID:21025            优先队列+贪心 详解

                   时间复杂度:Θ() 空间复杂度:Θ()

http://blog.csdn.net/cax1165/article/details/52331383


by 33475 八月 26, 2016, 8:18 p.m.

Solution_ID:21019            贪心。比楼上简洁的思路和代码。

                   时间复杂度:Θ(o(n)) 空间复杂度:Θ(o(n))

/*

  刚开始想了一个贪心思路,不知道对不对,然而真的就对了,只不过是O(n^2)的,TLE,

  然后用优先队列优化就过了。

  贪心思路首先我们明确,找前i个住户一定是在i-1的基础上找的,具体方法是记录当前我们

  最远找到的村庄位置now,因为当你往回找和往前找时走的路程是不同的,对于now来说,

  我们有两种决策,一种是向上找,一种是向下找,找到最大值加入ans,这样是O(n^2)的方法。

  然而我们发现向上找的部分会随now的变大而逐渐不浪费时间,向下找的部分则会重复找很多次,

  所以我们搞一个优先队列,再记录一个当前最远的入队元素位置from,每次当我们更新now时,

  就把from+1到now内的元素放入优先队列,这样我们在下一次向下找的时候就不用再循环一遍,

  而是直接从优先队列中取头元素就好了。 

*/

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#define M 100010

using namespace std;

int n,ans;

struct node

{

int v,pos;

bool operator< (node x)const

{

return v<x.v;

}

};node a[M],b;

priority_queue<node> q;

int main()

{

scanf("%d",&n);

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

 scanf("%d",&a[i].pos);

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

 scanf("%d",&a[i].v);

b.v=0;b.pos=0;

q.push(b);

int now=0,from;

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

{

b=q.top();

int mx=b.v,p=0;

for(int j=now+1;j<=n;j++)

 if((a[j].pos-a[now].pos)*2+a[j].v>mx)

 {

  mx=(a[j].pos-a[now].pos)*2+a[j].v;

  p=j;

 }

if(p)

{

b.pos=p;b.v=mx;

from=now;now=p;

q.push(b);

for(int j=from+1;j<now;j++)

 q.push(a[j]);

}

node b=q.top();

ans+=b.v;

q.pop();

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

}

return 0;

}


by 35543 八月 26, 2016, 5:11 p.m.

Solution_ID:21016            贪心

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define maxn 100010

#define maxx 10010

using namespace std;

int n,tot,far,ans,now,a[maxn],b[maxn],c[maxn];

struct node

{

int w;

int v;

bool operator < (node x)const

{

return v<x.v;

}

}e[maxn],ha;

priority_queue<node>q;

int cmp(node x,node y)

{

if(x.w<y.w)return 1;

if(x.w==y.w&&x.v>y.v)return 1;

return 0;

}

int main()

{

int i,j,k;

scanf("%d",&n);

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

 scanf("%d",&e[i].w);

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

 scanf("%d",&e[i].v);

sort(e+1,e+n+1,cmp);

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

{

if(e[i].w!=e[i-1].w)

{

tot++;

b[tot]=i;

a[tot]=i;

c[tot]=e[i].w;

}

else a[tot]=i;

}

ha.w=0;

ha.v=0;

q.push(ha);

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

{

ha=q.top();

int mx=ha.v,p=now;

for(j=now+1;j<=tot;j++)

{

int t=b[j];

if(e[t].v+(e[t].w-far)*2>mx)

{

mx=e[t].v+(e[t].w-far)*2;

p=j;

}

}

int t=b[p];

e[t].v+=(e[t].w-far)*2;

far=e[t].w;

for(j=a[now]+1;j<=a[p];j++)

 q.push(e[j]);

now=p;

ha=q.top();

q.pop();

ans+=ha.v;

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

}

return 0;

}


by 34879 八月 26, 2016, 3:21 p.m.