Cao, imam problem sa zadatkom popunjavanje praznina. Koliko sam shvatio ideja bi trebalo da bude samo da gledamo lokalne maksimume i da nadjemo izmdju kojih mozemo dodati najveci broj kutija, ali mi ne porlazi nijedan test primer iako je na nekim mojim i datim test primerima sve okej.
Link ka zadatku
https://petlja.org/biblioteka/r/problemi/zbirka-napredni-nivo/popunjavanje_praznina
Moj kod:
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[50050];
vector loc_max;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
if(i==0 && arr[i]>=arr[i+1]){
loc_max.push_back(i);
}
else if(i==n-1 && arr[i]>arr[i-1]){
loc_max.push_back(i);
}
else if(arr[i]>=arr[i+1] && arr[i]>arr[i-1]){
loc_max.push_back(i);
}
}
long long sum=0;
for(int i=0; i<loc_max.size()-1; i++){
int start=loc_max[i];
int end;
int j=i+1;
while(j+1<loc_max.size() && arr[loc_max[j]]<arr[loc_max[j+1]]){
j++;
}
end=loc_max[j];
i=j-1;
int maxi = min(arr[start], arr[end]);
for(int j=start+1;j<end;j++){
sum+= maxi-arr[j];
}
}
cout<<sum;
return 0;
}
Da li biste mogli da mi date neku ideju za resenje. Hvala u napred!