#17819: 解題思路


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 :
2019-05-30 22:56:25
d164. 七、最佳选择 -- NOI冬令营 | From: [39.8.203.54] | 發表日期 : 2019-05-23 16:46

這題如果要快,可以在讀品質數過程一同進行找品質數最大和

每頭牛的品質數用陣列存,每讀一筆累加一次,當選滿指定頭數後比大小,之後減去剛剛選定的開頭的牛

當比大小重複 N 次後,結束迴圈並輸出答案

範例 : ( 假設測資如下 )


5 3

10

3

9

7

1

宣告 max 代表最大和,sum 代表累加的總和,rear 、i 代表索引,count 代表組數,全部初始化 = 0

陣列 cow [ 10000 ] 代表等等存的品質數

讀進 5 頭牛 選 3 頭後,開始迴圈

i = 0 存 cow [ 0 ],同時 sum += cow [ 0 ], i + 1 < 3 代表還沒選滿 3 頭

i = 1 存 cow [ 1 ],同時 sum += cow [ 1 ], i + 1 < 3 代表還沒選滿 3 頭 ( 此時 rear 等於 0 )

 

i = 2 存 cow [ 2 ],同時 sum += cow [ 2 ], i + 1 >= 3 代表選滿 3 頭了,比較 max、sum 大小,然後 sum -= cow [ rear++ ],count ++ 

i = 3 存 cow [ 3 ],同時 sum += cow [ 3 ], i + 1 >= 3 代表選滿 3 頭了,比較 max、sum 大小,然後 sum -= cow [ rear++ ],count ++

i = 4 存 cow [ 4 ],同時 sum += cow [ 4 ], i + 1 >= 3 代表選滿 3 頭了,比較 max、sum 大小,然後 sum -= cow [ rear++ ],count ++

此時離開第一個迴圈 進入第二個,直到 count == 5 為止

count = 3 ,i = 0 ,sum += cow [ i ],比大小,sum -= cow [ rear++ ]

count = 4 ,i = 1 ,sum += cow [ i ],比大小,sum -= cow [ rear++ ]

 

count = 5 跳開迴圈,輸出 max 即是答案

 
ZeroJudge Forum