MODDI
Joined: 27/12/2017 18:17:00
Messages: 39
Offline
|
????? ?? ?????? ?? ?????? 8 ????????, ?? ?????????? ?? ???? ?? ?????, ???? ?? ?? ???????
This message was edited 2 times. Last update was at 19/08/2020 16:11:55
|
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
|
MODDI wrote:Кодов ми работи на првите 8 случаеви, на останатите ми паѓа на време, како да го убрзам кодов?
Твојот алгоритам има преголема сложеност. Оваа задача може да се реши во линеарно време O(N). Така да, не може секогаш да се "убрза" некој почнат код, и треба да се внимава да направиме анализа на алгоритамот пред да почнеме да решаваме (за да не изгубиме време на пишување на решение кое нема да освои онолку поени колку што очекуваме, па да почнеме од почеток со куцање на нешто друго).
Е сега, во однос на задачата. Размисли дали можеме да пресметаме неколку работи однапред, за да не ги правиме при секоја ротација. Еве еден начин како може да се реши задачава со тој пристап:
Нека имаме низа frontSum[i] која што ни го памети збирот на првите i броеви - т.е. A[1] + A[2] + A[3] + ... + A[i].
Нека имаме низа backSum[i] која што ни го памети збирот на сите броеви од i-тиот до N-тиот - т.е. A[i] + A[i+1] + ... + A[N]
Нека имаме низа frontMin[i] која што го памети најмалиот збир од последователни броеви завршувајќи со i - т.е. min(A[1], A[1]+A[2], ... A[1] + A[2] + ... + A[i])
Нека имаме низа backMin[i] која што го памети најмалиот збир од последователни броеви почнувајќи со i - т.е. min(A[i], A[i]+A[i+1], A[i]+A[i+1]+A[i+2], ...)
Со овие низи, проверките се доста едноставни за секоја ротација. На пример, ако решиме да ја разгледуваме i-тата ротација (онаа која почнува со i-тиот број), треба само да провериме дали се исполнети овие два услови:
1) backMin[i] >= 0 (со ова го проверуваме потребниот услов за сите броеви од i-тиот до N-тиот, т.е. дали A[i] >= 0, дали A[i] + A[i+1] >= 0, итн)
2) backSum[i] + frontMin[i-1] >= 0 (ако ротацијата почнува од i-тиот елемент, тогаш таа по броевите A[i], A[i+1], ... A[N] ќе заврши со броевите A[1], A[2], А[i-1], па со овој чекор го проверуваме условот за тие следни броеви. Види како истиот е сличен на првиот, но додаваме backSum[i]).
За првата ротација не мора да го проверуваме вториот услов, бидејќи таму нема прелевање (т.е. броевите се A[1], A[2], ... A[N]). Еве и код ако уште не е јасно:
|