Mai intai trebuie sa te autentifici.
Diferente pentru deque-si-aplicatii intre reviziile #41 si #42
Nu exista diferente intre titluri.
Diferente intre continut:
În practică, programul poate arăta în felul următor: == code(cpp) |
#include <fstream> #include <deque> #include <algorithm> using namespace std; #define MAXN 100005 typedef int (*PF)(const int , const int ) ; int V[MAXN];
// ...
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(V[p],V[deq.back()]); deq.pop_back()) ;
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()) ;
returnV[deq.front()];
return S[deq.front()];
}
int main(void) { ifstream in("sir.in"); ofstream out("sir.out"); int n, X, Y, Z; int length = 0, start, stop, j = 0; in >> n >> X >> Y >> Z; for (int i = 1; i <= n; ++ i) { in >> V[i];
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)
if (i - j >= length) length = i - j, start = j + 1, stop = i;
// compară cu rezultatul de până acum
}
length > 0 ? out << length << " " << start << " " << stop : out << -1; in.close(), out.close(); return 0;
// ...
} ==