黑板上有n個數字寫成一排，現在每次選擇兩個相鄰的數字，把比較小的那個 數字擦掉(如果兩個數字一樣大，那麼擦掉任何一個都可以。)然而，這些步驟需要花費，這個花費恰好等於留下來的那個數字(比較大的那個)。
請問經過n-1次操作，黑板上會剩下的那個數字是多少？
你以為問題這麼簡單嗎？錯!
真正的問題是：
請問經過n-1次操作，黑板上會剩下最大的那個數字，所有操作方法中，最小總花費是多少？
輸入說明 ：
輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=1,000,000)代表黑板上數字的個數。
接下來有n列，每列有一個正整數(1<=數字<=109)依序代表黑板上的每個數字。
輸出說明 ：
請輸出經過n-1次操作之後，所需的最小總花費。
範例輸入 ：
5
7
4
5
2
5
範例輸出 ：
22
提示 ：
消掉4、花費5；
消掉2、花費5；
消掉5、花費5；
消掉5、花費7；
總花費是5+5+5+7=22。
Private Sub Form_Load()
回覆刪除Dim y(1000000) As Integer
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Input #1, n
Max = 0
For i = 1 To n
Input #1, x
y(i) = x
Next
c = n
Min = y(1)
ans = 0
Do
For i = 1 To n
If Min > y(i) And y(i) <> 0 Then Min = y(i): d = i
Next
If y(d + 1) > y(d - 1) Then
ans = ans + y(d - 1)
For i2 = d To x - 1
y(i2) = y(i2 + 1)
Next
Else
ans = ans + y(d + 1)
For i2 = d To x - 1
y(i2) = y(i2 + 1)
Next
End If
c = c - 1
Loop Until c = 2
If y(1) < y(2) Then
ans = ans + y(2)
Else
ans = ans + y(1)
End If
Print #2, ans
Close
Close
End
End Sub
Dim a(), g, s, t As Integer
回覆刪除Private Sub Form_Load()
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Input #1, n
ReDim a(Val(n))
g = 999
For i = 1 To Val(n)
Input #1, x
a(i) = Val(x)
If a(i) < g Then g = a(i): s = i
Next i
t = UBound(a)
Do
If t = LBound(a) + 1 Then Print #2, pay: End
If a(s - 1) >= a(s + 1) And a(s + 1) <> 0 Then
If a(s) <= a(s + 1) Then a(s) = 0: pay = pay + a(s + 1): g = 999
ElseIf a(s - 1) < a(s + 1) And a(s - 1) <> 0 Then
If a(s) <= a(s - 1) Then a(s) = 0: pay = pay + a(s - 1): g = 999
ElseIf a(s - 1) > a(s + 1) And a(s + 1) = 0 Then
a(s) = 0: pay = pay + a(s - 1): g = 999
End If
For i = 1 To t
If a(i) = 0 And i <> t Then a(i) = a(i + 1): a(i + 1) = 0
If a(i) < g And a(i) <> 0 Then g = a(i): s = i
Next i
For i = 1 To t
If a(i) = 0 Then t = t - 1
Next i
Loop
Close #2
Close #1
End
End Sub