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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【迈克杯二弹】【物种起源】  

2013-11-03 18:26:45|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   这一题一开始还以为是dp,后来发现一个规律,那就是最后的答案只与M[]的拐点有关,拐点就是M[]的在某一范围的极大值或者极小值,然后我们只需要先求出拐点个数,然后将大的数放在高拐点上,将低的数放在矮拐点上就可以了。另外我们也不需要考虑拐点具体怎么放,我们只要对w[]快排一次,然后将高拐点个数max的前max个最大数相加,再减去低拐点个数的最小值,最后再调整一下边界就可以了
只可惜比赛的时候边界没判断好,结果只拿了20分,明明就2句话的事.....AC啊....Rating啊...
===================================================================

program wuzhong;
var n:longint;
    m,w:array[1..400000]of int64;

procedure init;
var i:longint;
begin
  read(n);
  for i:=1 to n do read(m[i]);
  for i:=1 to n do read(w[i]);
  if n=1 then begin write(0);halt;end;
  if n=2 then begin write(abs(w[2]-w[1]));halt;end;
end;

procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
  i:=l;j:=r;
  x:=w[(l+r)shr 1];
  repeat
   while w[i]<x do inc(i);
   while w[j]>x do dec(j);
   if i<=j then begin
     y:=w[i];w[i]:=w[j];w[j]:=y;
     inc(i);dec(j);end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure main;
var i:longint;
    min,max:longint;
    ans:int64;
begin
  min:=0;max:=0;
  if m[1]<m[2] then inc(min)
               else inc(max);
  if m[n]<m[n-1] then inc(min)
                 else inc(max);
  for i:=2 to n-1 do
   begin
     if (m[i]>m[i-1])and(m[i]>m[i+1]) then inc(max);
     if (m[i]<m[i-1])and(m[i]<m[i+1]) then inc(min);
   end;
  qsort(1,n);
  ans:=0;
  for i:=n downto n-max+1 do ans:=ans+w[i]*2;
  for i:=1 to min do ans:=ans-w[i]*2;
  if m[1]<m[2] then ans:=ans+w[min]
               else ans:=ans-w[n-max+1];
  if m[n]<m[n-1] then
   if m[1]<m[2] then inc(ans,w[min-1])
                else inc(ans,w[min])
                else
   if m[1]<m[2] then dec(ans,w[n-max+1])
                else dec(ans,w[n-max+2]);
  write(ans);
end;

begin
  init;
  main;
end.

  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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