Cześć, mam takie zadanie:
Żołnierze powinni ustawić się na planie kwadratu, tak, żeby każdych dwóch żołnierzy mieszkających w tym samym budynku stało na apelu obok siebie, czyli w tym samym rzędzie kwadratu.
Ponadto, żołnierze z poszczególnych budynków muszą stać po kolei, tzn. poczynając od pierwszego rzędu:
pierwszy budynek, drugi budynek, itd. znajdź najmniejszą długość boku takiego kwadratu.
Liczba całkowita n (1 ≤ n ≤ 500.000), oznacza liczbę budynków, w których mieszkają żołnierze, liczba żołnierzy w każdym budynku jest dodatnia i nie większa niż 10^9
Mój kod:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
long long n,maksk,mink,pom,i,j,D;
cin>>n;
long long t[n+1];
long long s;
bool dosc;
maksk=0;
s=0;
for(i=1;i<=n;i++){
cin>>t[i];
if(maksk<t[i]) maksk=t[i];
s+=t[i];
}
//wyznaczam min rzedow - pierwiastek z sumy lub max ilosc osob - zaokr.w gore
pom=ceil(sqrt(s));
if(pom>maksk)mink=pom;
else mink=maksk;
//wyznaczam max rzedow - pierwiastek z ilosci domow * max ilosc osob - zaokr.w gore
pom=ceil(sqrt(n*maksk));
if(pom>maksk) maksk=pom;
if(maksk==mink) cout<<maksk;
else //sprawdzam czy wszyscy sie zmieszcza w min ilosci rzedow a jak nie to mink++ az do maksk
do{
dosc=false;
D=n;
i=1;
while(i<n && !dosc)
{
pom=mink-t[i];
j=i+1;
while(pom>=0 && !dosc && j<=n)
if(pom>=t[j]){
pom-=t[j];
D--;
j++;
if(D<=mink) dosc=true;
}
else{
i=j;
break;
}
}
if(dosc){
cout<<mink;
break;
}
else{
mink++;
if(mink==maksk){
cout<<mink;
break;
}
}
}while(!dosc);
}
Program działa, sprawdzałem czy nie wywala się na maksymalnych liczbach w zadaniu ( wziąłem sumę =10^9 * 500.000), ale na kilku testach wychodzi mi błędny wynik...
Rozumiem przekroczenie limitu czasu, nad tym mogę popracować, ale nie ogarniam jakie dane można podać aby wyszła błędna odp.
Proszę o uwagi, ewentualnie może ktoś ma inny pomysł na rozwiązanie problemu, dzięki.