1657: [Usaco2006 Mar]Mooo 奶牛的歌声

1657: [Usaco2006 Mar]Mooo 奶牛的歌声

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 526  Solved: 365

[Submit][Status]

Description

Farmer John's N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This "moo" travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow's right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.

Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。

Input

* Line 1: A single integer, N.

* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.

    第1行:一个正整数N.

    第2到N+1行:每行包括2个用空格隔开的整数,分别代表站在队伍中第i个位置的奶牛的身高以及她唱歌时的音量.

Output

* Line 1: The loudest moo volume heard by any single cow.

    队伍中的奶牛所能听到的最高的总音量.

Sample Input

3 4 2 3 5 6 10 INPUT DETAILS: Three cows: the first one has height 4 and moos with volume 2, etc.

Sample Output

7

HINT

     队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声,于是她能听到的总音量为2+5=7.虽然她唱歌时的音量为10,但并没有奶牛可以听见她的歌声.

Source

Silver

题解:萌萌哒我赶脚此题超级神似Bzoj1660,这道题还是直接线段树维护即可,方法类似bzoj1660(话说今天才发现bzoj1660里面的b数组根本没用到啊呵呵。。。)

 1 var
 2    i,j,k,l,m,n:longint;
 3    a,b,c,e:array[0..500000] of longint;
 4 function max(x,y:longint):longint;
 5          begin
 6               if x>y then max:=x else max:=y;
 7          end;
 8 function min(x,y:longint):longint;
 9          begin
10               if x<y then min:=x else min:=y;
11          end;
12 procedure build(x,y,z:longint);
13           begin
14                if (x=y) then
15                   begin
16                        a[z]:=c[x];
17                        b[z]:=x;
18                   end
19                else
20                    begin
21                         build(x,(x+y) div 2,z*2);
22                         build((x+y) div 2+1,y,z*2+1);
23                         a[z]:=max(a[z*2],a[z*2+1]);
24                    end;
25           end;
26 function getright(x,y,z,l,r,t:longint):longint;
27          var
28             i,j,k:longint;
29          begin
30               if l>r then exit(-1);
31               if c[l]>t then exit(l);
32               if a[z]<=t then exit(-1);
33               if (l=r) or (x=y) then exit(-1);
34 
35               i:=getright(x,(x+y) div 2,z*2,l,min(r,(x+y) div 2),t);
36               if i=-1 then
37                  getright:=getright((x+y) div 2+1,y,z*2+1,max(l,(x+y) div 2+1),r,t)
38               else
39                   getright:=i;
40          end;
41 function getleft(x,y,z,l,r,t:longint):longint;
42          var
43             i,j,k:longint;
44          begin
45               if l>r then exit(-1);
46               if a[z]<=t then exit(-1);
47               if c[r]>t then exit(r);
48               if (x=y) or (l=r) then exit(-1);
49 
50               i:=getleft((x+y) div 2+1,y,z*2+1,max(l,(x+y) div 2+1),r,t);
51               if i=-1 then
52                  getleft:=getleft(x,(x+y) div 2,z*2,l,min(r,(x+y) div 2),t)
53               else
54                   getleft:=i;
55          end;
56 begin
57      readln(n);
58      for i:=1 to n do
59          readln(c[i],e[i]);
60      build(1,n,1);
61      fillchar(b,sizeof(b),0);
62      for i:=1 to n do
63          begin
64               j:=getleft(1,n,1,1,i-1,c[i]);
65               k:=getright(1,n,1,i+1,n,c[i]);
66               if j<>-1 then b[j]:=b[j]+e[i];
67               if k<>-1 then b[k]:=b[k]+e[i];
68          end;
69      l:=0;
70      for i:=1 to n do
71          l:=max(l,b[i]);
72      writeln(l);
73 end.
74                     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1741: [Usaco2005 nov]Asteroids 穿越小行星群

1741: [Usaco2005 nov]Asteroids 穿越小行星群 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

2766
来自专栏HansBug's Lab

1634: [Usaco2007 Jan]Protecting the Flowers 护花

1634: [Usaco2007 Jan]Protecting the Flowers 护花 Time Limit: 5 Sec  Memory Limit:...

3268
来自专栏HansBug's Lab

1653: [Usaco2006 Feb]Backward Digit Sums

1653: [Usaco2006 Feb]Backward Digit Sums Time Limit: 5 Sec  Memory Limit: 64 MB ...

2744
来自专栏HansBug's Lab

3314: [Usaco2013 Nov]Crowded Cows

3314: [Usaco2013 Nov]Crowded Cows Time Limit: 1 Sec  Memory Limit: 128 MB Submit...

2665
来自专栏HansBug's Lab

1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

3037
来自专栏HansBug's Lab

2020: [Usaco2010 Jan]Buying Feed, II

2020: [Usaco2010 Jan]Buying Feed, II Time Limit: 3 Sec  Memory Limit: 64 MB Subm...

2817
来自专栏HansBug's Lab

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场 Time Limit: 5 Sec  Memory Limit: 64 ...

3386
来自专栏HansBug's Lab

1724: [Usaco2006 Nov]Fence Repair 切割木板

1724: [Usaco2006 Nov]Fence Repair 切割木板 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

2927
来自专栏HansBug's Lab

2015: [Usaco2010 Feb]Chocolate Giving

2015: [Usaco2010 Feb]Chocolate Giving Time Limit: 10 Sec  Memory Limit: 162 MB S...

3136
来自专栏HansBug's Lab

1664: [Usaco2006 Open]County Fair Events 参加节日庆祝

1664: [Usaco2006 Open]County Fair Events 参加节日庆祝 Time Limit: 5 Sec  Memory Limit:...

2705

扫码关注云+社区

领取腾讯云代金券