由于燃料为流动性物质。
所以利用任意一个有水的地方往左右延伸其水平面一样高,
可以先从左以尽量高的起点往前延伸遇到顶,下降到顶。遇到地面,上升到与地面同高度。
这样再从右往左贪心一边去每个点的最小值即可。
#include <set> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int maxn = 1000100; int L[maxn],R[maxn]; int n,p[maxn],s[maxn]; int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&p[i]); } for(int i=1;i<=n;i++){ scanf("%d",&s[i]); } int level = s[1]; for(int i=1;i<=n;i++){ if(level<p[i]) level=p[i]; if(level>s[i]) level=s[i]; L[i] = level; // cout<<i<<" "<<level<<endl; } level = s[n]; for(int i=n;i>=1;i--){ if(level<p[i]) level=p[i]; if(level>s[i]) level=s[i]; R[i] = level; } int res=0; for(int i=1;i<=n;i++){ //cout<<min(L[i],R[i])<<endl; res+=min(L[i],R[i])-p[i]; } printf("%d\n",res); } return 0; }