Проблема взята из недавнего конкурса на Codechef.В соответствии с проблемой, для данного массива длины N найдите максимальное среднее число чисел любого смежного подмассива длины между A и B.
Теперь вот логика, которую я использовал.Я провел в цикле итерацию по всей возможной длине смежного подмассива K от A до B. Затем для каждого такого K я использовал механизм скользящего окна, чтобы найти максимальную сумму смежных элементов массива.Затем я проверяю, меньше ли уже сохраненный ответ (среднее значение), чем текущий максимум / K, и обновляю ответ.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,b,a;
cin>>n>>b>>a;
long long arr[n+1];
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
double ans=0;
for(int k=a;k<=b;k++)
{
long long maxi=0;
for(int i=1;i<=k;i++)
{
maxi=maxi+arr[i];
}
long long l=maxi;
for(int i=k+1;i<=n;i++)
{
l=l+arr[i]-arr[i-k];
maxi=max(maxi,l);
}
double x=(double)(((double)(maxi))/(double)(k));
ans=max(ans,x);
}
cout<<ans<<endl;
}
}
Однако после реализации моей логики, как показано, я получаю неправильные ответы дажехотя я не знаю, насколько они отличаются от фактического ответа, так как я не получил ничего неправильного в моих процессах отладки.
Следующее является правкой: мой предыдущий код и следующий одинаковы?
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,b,a;
cin>>n>>b>>a;
long long arr[n+1];
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
long double ans=0;
for(int k=a;k<=b;k++)
{
long long l=0;
for(int i=1;i<=k;i++)
{
l=l+arr[i];
}
ans=max(ans,(long double)(((long double)(l))/(long double)(k)));
for(int i=k+1;i<=n;i++)
{
l=l+arr[i]-arr[i-k];
ans=max(ans,(long double)(((long double)(l))/(long double)(k)));
}
}
cout<<ans<<endl;
}
}