Diferente pentru deque-si-aplicatii intre reviziile #48 si #49

Nu exista diferente intre titluri.

Diferente intre continut:

În practică, programul poate arăta în felul următor:
== code(cpp) |
// ...
// S şirul de numere iniţial şi N lungimea sa
deque <int> min_deq, max_deq;
 
typedef int (*PF)(const int , const int ) ;
 
int min_fct(const int a, const int b) { return a < b; }
 
int max_fct(const int a, const int b) { return a > b; }
 
void push_in(deque <int>& deq, const int p, PF compare) {
    for (; !deq.empty() && compare(S[p], S[deq.back()]); deq.pop_back()) ;
    deq.push_back(p);
}
 
int query(deque <int>& deq, const int j) {
    for (; !deq.empty() && deq.front() <= j; deq.pop_front()) ;
    return S[deq.front()];
}
 
int main(void) {
    // ...
    for (int i = 1; i <= N; ++ i) {
        push_in(min_deq, i, min_fct);
        push_in(max_deq, i, max_fct);
        while ((j < i - Y || query(max_deq, j) - query(min_deq, j) > Z) && j < i - X)
            j ++;
        // (j, i] este intervalul candidat la soluţia pentru pozitia i
        if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
            // compară cu rezultatul de până acum
    }
    // ...
}
Subalgoritmul push_in(deque, întreg p, funcţia fct) este:
    cât timp (!deque.empty() şi fct(S[p], S[deque.back()])) execută
        deque.pop_back();
    deque.push_back(p);
Sfârşit;
 
Funcţia query(deque, întreg j) este:
    cât timp (!deque.empty() şi deque.front() &le; j) execută
        deque.pop_front();
    return S[deque.front()];
Sfârşit;
 
Algoritmul este:
    lg = 0;
    pentru i = 1, N execută
        // funcţia min(a, b) întoarce true dacă a < b
        inserează(min_deq, i, min);
        // funcţia max(a, b) întoarce true dacă a > b
        inserează(max_deq, i, max);
        cât timp ((j < i - Y sau query(max_deq, j) - query(min_deq, j) > Z) şi j < i - X) execută
            j = j + 1;
        // (j, i] este intervalul candidat la soluţia optimă pentru poziţia i
        dacă (j <= i - X) şi (query(max_deq, j) - query(min_deq, j) &le; Z) atunci
            dacă (lg >= i - j) atunci
                lg = i - j, start = j + 1, stop = i;
    sfârşit_pentru
 
    dacă (lg > 0) then
        scrie lg, start, stop;
    altfel
        scrie -1;
Sfârşit.
==
Complexitatea finală va fi $O(N)$.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.