g734 - 110北二5.海洋世界
題目描述
題目給定 n 個珊瑚礁的高度 a[i] 和 m 個能量值。要求找到兩個珊瑚礁 i 和 j，使得 j > i 且 a[i] * (b[j] - b[i]) >= m，其中 b[i] 是前 i 個珊瑚礁能量值的總和。目標是最小化 a[i] * (b[j] - b[i]) 的值。如果找不到滿足條件的珊瑚礁對，則輸出 -1。
解題思路
本題的核心思想是利用動態規劃尋找滿足能量條件的最優珊瑚礁組合。首先，計算能量的前綴和 b[i]。然後，使用 DP 陣列 DP 從左到右遍歷，記錄每個高度的珊瑚礁的最近索引。同時，計算 l[i]，表示高度為 a[i] 的珊瑚礁左側滿足條件的最近索引。類似地，從右到左遍歷，計算 r[i]，表示高度為 a[i] 的珊瑚礁右側滿足條件的最近索引。最後，遍歷所有珊瑚礁，檢查 l[i] 和 r[i] 是否有效，並計算滿足條件的能量成本，更新最小成本 ans。
複雜度分析
- 時間複雜度: O(n * 100 + n) = O(n)。其中 n 是珊瑚礁的數量，100 是高度的最大值。
- 空間複雜度: O(n + 105) = O(n)。其中 n 是珊瑚礁的數量，105 是 DP 陣列的大小。
程式碼
#include <iostream>
using namespace std;
int n,m,ans=1e9,a[100005],b[100005],DP[105],r[100005],l[100005];//higher next
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=0;i<101;++i)
DP[i]=-1;
for(int i=0;i<n;++i){
cin >> a[i];
int lv=-1;
for(int j=a[i];j<=100;++j)
lv=max(lv,DP[j]);
l[i]=lv;
DP[a[i]]=i;
}
for(int i=1;i<n;++i){
cin >> b[i];
b[i]+=b[i-1];
}
for(int i=0;i<101;++i)
DP[i]=1e9;
for(int i=n-1;i>=0;--i){
int rv=1e9;
for(int j=a[i];j<=100;++j)
rv=min(rv,DP[j]);
r[i]=rv;
DP[a[i]]=i;
}
for(int i=0;i<n;++i){
if(l[i]!=-1&&a[i]*(b[i]-b[l[i]])>=m)ans=min(ans,a[i]*(b[i]-b[l[i]]));
if(r[i]!=1e9&&a[i]*(b[r[i]]-b[i])>=m)ans=min(ans,a[i]*(b[r[i]]-b[i]));
}
if(ans==1e9)
cout << "-1";
else
cout << ans;
}