d652 - 貪婪之糊
題目描述
題目描述了「貪婪之糊」之間的一個遊戲，遊戲規則是三隻貪婪之糊中，中間的被兩側的吸收。目標是找到一種吸收順序，使得遊戲產生的總污染值最小，污染值等於被吸收貪婪之糊的大小乘以其兩側貪婪之糊的大小。最終的勝利者是左邊和右邊的貪婪之糊。
解題思路
這個問題可以通過貪婪策略解決。首先找到最小的貪婪之糊，然後依次計算以該最小貪婪之糊為中心，向左和向右吸收貪婪之糊的污染值。最後，考慮吸收掉最左邊和最右邊的貪婪之糊的污染值，並選擇最小的總污染值。程式碼中，首先找到最小的貪婪之糊及其索引。然後，分別計算以最小貪婪之糊為中心向左和向右吸收貪婪之糊的污染值。最後，計算吸收掉最左邊和最右邊貪婪之糊的污染值，並將所有污染值加總。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int a[n],ans=0,minn=101,mi;
for(int i=0;i<n;++i){
cin >> a[i];
if(a[i]<minn){
minn=a[i];
mi=i;
}
}
for(int i=mi+1;i<n-1;++i)
ans+=a[mi]*a[i]*a[i+1];
for(int i=mi-1;i>0;--i)
ans+=a[mi]*a[i]*a[i-1];
if(mi!=0&&mi!=n-1)
ans+=a[0]*a[mi]*a[n-1];
cout << ans;
}