#38693: 簡單思路 O(n)
qerpzzea@gmail.com
(賽希爾 cecill(陳宥穎))
學校
:
高雄市立中正高級中學
編號 : 169400
來源 : [163.32.60.236]
最後登入時間 ：
2024-05-01 11:18:53
c435. MAX ! MAX ! MAX !
| From: [118.171.6.113] |
發表日期
:
2023-12-17 20:00
a為輸入的陣列
用個變數來存目前掃描到的最大值(假設此變數為x),由於i必須嚴格<j,所以當往後掃描a[i]時有比x還大的值,就可以把x更新,之後用此值減去a[i]必可以產生更優解
然後除了a[0],每次都用x-a[i]去更新答案(取max)
證明: (x1為更新後的x) 由於是往後掃描所以符合題目要求(i<j),且x1>x 所以對於任何a[i], x1-a[i]>x-a[i]
#38709: Re: 簡單思路 O(n)
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2024-05-05 06:17:12
c435. MAX ! MAX ! MAX !
| From: [210.71.71.103] |
發表日期
:
2023-12-18 12:26
a為輸入的陣列
用個變數來存目前掃描到的最大值(假設此變數為x),由於i必須嚴格<j,所以當往後掃描a[i]時有比x還大的值,就可以把x更新,之後用此值減去a[i]必可以產生更優解
然後除了a[0],每次都用x-a[i]去更新答案(取max)
證明: (x1為更新後的x) 由於是往後掃描所以符合題目要求(i<j),且x1>x 所以對於任何a[i], x1-a[i]>x-a[i]
有點小亂
敘述中的 $a[i]$ 和 $i$ 表示的「$i$」是不一樣的東西
#38710: Re: 簡單思路 O(n)
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2024-05-05 06:17:12
c435. MAX ! MAX ! MAX !
| From: [210.71.71.103] |
發表日期
:
2023-12-18 12:32
稍微改了一些:
$a$ 為輸入的陣列
遍歷 $a_n$
存目前掃描到的最大值 $a_i$
由於 $i$ 必須嚴格小於 $j$，所以當往後掃描 $a_n$ 時有比 $a_i$ 還大，就可以把 $a_i$ 更新，之後用此值減去 $a_n$ 必可以產生更優 $(a_i-a_j)$ 解
證明: （$a_{i'}$ 為更新後的 $a_i$） 由於 $a_n$ 是往後掃描所以符合題目要求 $(i<j)$，且 $a_{i'}>a_i$ 所以對於任何 $a_j$，必符合 $a_{i'}-a_j>a_i-a_j$
ZeroJudge Forum