注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

salesman  

2015-12-03 13:54:33|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

salesman - 杨鸿飞 - 一个叫杨鸿飞的人的博客
题目贴的有点大,谅解。
==================================================
        这题是今年NOIP的最后一题,我只拿了60分,其实这题有很多种做法,其主要思路,都是差不多的。
1,找到第一大。时间,O(n)。
2,预处理左边,为了在比较快的的时间找最优值,这里用一个倒推的方法最快。预处理时间O(n),查找时间O(1)。
3,预处理右边,这里就涌现了许多方法
      (1)数组计数:预处理时间O(n),查找时间O(1000)。
      (2)胜者树:预处理时间O(n),查找时间O(logn)。
      (3)优先队列:预处理时间O(n),查找时间O(logn)。
      (4)单调队列:预处理时间O(nlogn),查找时间O(1)。
4,有了预处理,就可以在比较快的的时间,找到左边的最优解和右边的最优解,从中在选一些最优解和维护,这样答案就出来了。
思路图:
salesman - 杨鸿飞 - 一个叫杨鸿飞的人的博客
看了图后,懂得差不多了吧。下面开始说做法:
==================================================
(一)、数组计数
==================================================
(二)、胜者树
        胜者树有个优势,就是可以在logn的速度维护最大值,借此,就可以做出这题。

//winner tree
#include <iostream>
#include <cstdio>

using namespace std;

const int oo=2100000000;

struct Ttree
{
int v,p;
};

Ttree f[400100];
int d[100100],v[100100];
int tlong=0,n;
int maxp[100100];

void change(int p,int x)
{
v[p]=x;

int tp=p+tlong;
f[tp].v=x,
f[tp].p=p;

for (tp/=2; tp>0; tp/=2)
if (f[tp*2].v>f[tp*2+1].v)
f[tp].v=f[tp*2].v,
f[tp].p=f[tp*2].p;
else
f[tp].v=f[tp*2+1].v,
f[tp].p=f[tp*2+1].p;
}

int main()
{
freopen("salesman.in","r",stdin);
freopen("salesman.out","w",stdout);
/*=================read=================*/
scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d",&d[i]);
for (int i=0; i<n; i++) scanf("%d",&v[i]);
v[n]=-oo;
/*==============YCL_right===============*/
maxp[n-1]=n-1; maxp[n]=n;
for (int i=n-2; i>=0; i--)
{
int lastp=maxp[i+1];
int lastmax=d[lastp]*2+v[lastp];
int thismax=d[i]*2+v[i];
if (lastmax>thismax) maxp[i]=lastp;
else maxp[i]=i;
}
/*=============make_tree================*/
for (tlong=1; tlong<n; tlong*=2);
for (int i=1; i<tlong*2; i++)
f[i].v=v[n],f[i].p=n;
/*===============findmax================*/
int nowp=maxp[0];
/*===============CSH_tree===============*/
for (int i=0; i<nowp; i++) change(i,v[i]);
/*=================wrok=================*/
int ans=d[nowp]*2+v[nowp];
printf("%d",ans);
for (int i=1; i<n; i++)
{
int t=maxp[nowp+1];
int le=f[1].v;
int ri=(d[t]-d[nowp])*2+v[t];
if (t==n) ri=-oo;
if (le>ri)
{
ans+=le;
change(f[1].p,-oo); //维护
}
else
{
ans+=ri;
for (int i=nowp+1; i<t; i++)  //添加新元素进树

change(i,v[i]);
nowp=t;
//更新最远距离
}
printf("\n%d",ans);
}
return 0;
}


==================================================
(三)、优先队列
==================================================
(四)、单调队列

    由于选过的不选,这种单调性,可以将整个数组按照推销疲劳值排序成单调队列,剔除点pn对数中总疲劳值最大的点)右边的,然后从头扫描,也可以以平均o(1)的查找时间找到p左边的最大值;

//fly's
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstdio>

using namespace std;

struct Tp { int v,p; };

bool _cmp(Tp x,Tp y)
{
if (x.v==y.v && x.p<y.p) return true;
return x.v>y.v;
}

int d[100100],v[100100];
int maxp[100100];
Tp s[100100];
int ff[100100];

int main()
{
freopen("salesman.in","r",stdin);
freopen("salesman.out","w",stdout);

int n;
/*=================read=================*/
scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d",&d[i]);
for (int i=0; i<n; i++) scanf("%d",&v[i]);
/*==============YCL_right===============*/
maxp[n-1]=n-1; maxp[n]=n;
for (int i=n-2; i>=0; i--)
{
int lastp=maxp[i+1];
int lastmax=d[lastp]*2+v[lastp];
int thismax=d[i]*2+v[i];
if (lastmax>thismax) maxp[i]=lastp;
else maxp[i]=i;
}
/*===============findmax================*/
int nowp=maxp[0];
/*===============YCL_left===============*/
for (int i=0; i<n; i++)
s[i].v=v[i],s[i].p=i;
sort(s+0,s+n,_cmp);
/*=================wrok=================*/
int ans=d[nowp]*2+v[nowp];
printf("%d",ans);
int p=0;
ff[nowp]=1;
for (int i=1; i<n; i++)
{
for ( ; (ff[s[p].p]!=0)&&(p<n); p++); //降序查找

int t=maxp[nowp+1];
int le=s[p].v;
int ri=v[t]+(d[t]-d[nowp])*2;
if (t==n) ri=-210000000;

if (ri>le)
{
ans+=ri; nowp=t; //更新最远距离
ff[nowp]=1;
}
else
{
ans+=le;
p++; //向下一位
}
printf("\n%d",ans);
}

return 0;
}


==================================================
除外,江老师用贪心另有做法
(五)、贪心

//gogo's
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cstdio>

using namespace std;

struct Tp { int v,p; };

const int oo=2100000000;

bool _cmp(Tp x,Tp y)
{
if (x.v==y.v && x.p>y.p) return true;
return x.v>y.v;
}

int d[100100],v[100100];
int maxp[100100];
Tp s[100100];

int main()
{
freopen("salesman.in","r",stdin);
freopen("salesman.out","w",stdout);

int n;
/*=================read=================*/
scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d",&d[i]);
for (int i=0; i<n; i++) scanf("%d",&v[i]);
/*==============YCL_right===============*/
maxp[n-1]=n-1; maxp[n]=n; v[n]=-oo;
for (int i=n-2; i>=0; i--)
{
int lastp=maxp[i+1];
int lastmax=d[lastp]*2+v[lastp];
int thismax=d[i]*2+v[i];
if (lastmax>thismax) maxp[i]=lastp;
else maxp[i]=i;
}
/*===============findmax================*/
int nowp=maxp[0];
/*===============YCL_left===============*/
for (int i=0; i<n; i++)
s[i].v=v[i],s[i].p=i;
sort(s+0,s+n,_cmp);
/*=================wrok=================*/
printf("%d",d[nowp]*2+v[nowp]);
int p=0,sum=0; nowp=s[0].p;
for (int i=1; i<n; i++)
{
sum+=s[i-1].v;

int newp1=maxp[nowp+1];
int newp2=s[i].p;
if (nowp>newp2) newp2=nowp;

int fa1=v[newp1]+d[newp1]*2;
int fa2=s[i].v+d[newp2]*2; //两种方案

if (fa1>fa2) printf("\n%d",sum+fa1);
else printf("\n%d",sum+fa2); //选最优

nowp=newp2;
}

return 0;
}

==================================================
小小的一道题蕴含有多少解法啊!
 
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018