atcoder [Exception Handling ]题解

atcoder [Exception Handling ]题解

https://atcoder.jp/contests/abc134/tasks/abc134_c?lang=en

给定长为N的序列,下标从1到N。 对于每个元素,输出序列里缺少这个序列之后的最大值。

解法:

N が数千以下 (言語によっては数万以下) なら、各問で Ai 以外の N − 1 個の要素すべてに対してループ を回して最大値を直接求めても実行制限時間の 2 秒に間に合います。しかし実際には N は最大で 20 万であ り、この方針では C++ でも間に合う望みはありません。計算時間を削減する方針を以下に二つ示します。

方針 1: 場合分け

ほとんどの場合、問いの答えは N 個すべての要素のうちの最大の値 Amax です。唯一の例外は問いで取り 除かれる値 Ai が Amax と等しい場合で、この場合の答えはすべての要素のうち 2 番目に大きい値 Asecond (数列中に Amax が複数回現れる場合は Asecond = Amax とします) です。問いの処理を始める前に Amax と Asecond をあらかじめ求めておけば、各問を直ちに処理できます。なお、Asecond を最も簡単な実装で求める 方法は、与えられた数列をコピーして言語の標準ライブラリでソートすることでしょう (やや「余計」な計算 をすることになりますが十分高速です)。

方針 2: 両端から攻める

j = 0, 1, . . . , N − 1 に対し、A1, A2, . . . , Aj のうちの最大の値を leftj とします (ただし left0 = 0 としま す)。j ≥ 1 のとき leftj = max(leftj−1, Aj ) *1 であることに注意すると、これらの値は一周のループですべ て求められます。また、j = 2, . . . , N + 1 に対し、Aj , Aj+1, . . . , AN のうちの最大の値を rightj とします (ただし rightN+1 = 0 とします)。j ≤ N のとき rightj = max(rightj+1, Aj ) であることに注意すると、こ れらの値も一周のループですべて求められます。問いの処理を始める前にこれらの値をあらかじめ求めておけ ば、各問 i の答えを max(lefti−1,righti+1) として直ちに求められます。

import Data.List
 
main=do
    line<-getLine
    ctx<-getContents
    let p =[read x::Int | x<-lines ctx]
    let m=maxL p
    let r= length [1 | x<-p,(maxL p)==x]
    let s= if r==1 then maxL [x |x<-p ,x /= m] else m
 
    output p m s
    
maxL :: [Int]->Int
maxL [x] =x
maxL (x:xs) = max x (maxL xs)
 
output :: [Int]->Int->Int->IO()
output [] _ _ = return()
output (x:xs) m s
    | m/=s =do
         if x==m then putStrLn (show s) else putStrLn (show m )
         output xs m s
    | otherwise =do
         putStrLn (show m)
         output xs m s

发表评论

电子邮件地址不会被公开。 必填项已用*标注