Техникаи ду нишондиҳанда
Бифаҳмед, ки техникаи ду нишондиҳанда чӣ гуна кор мекунад
Муқаддима
Фарз мекунем ба мо массиви ва адади дода шудааст. Мо мехоҳем зермасиви -ро бо дарозии максималӣ ёбем, ки ҷамъбасти унсурҳои он аз зиёд набошад.
Бифаҳмед, ки техникаи ду нишондиҳанда чӣ гуна кор мекунад
Фарз мекунем ба мо массиви ва адади дода шудааст. Мо мехоҳем зермасиви -ро бо дарозии максималӣ ёбем, ки ҷамъбасти унсурҳои он аз зиёд набошад.
Ба ибораи дигар, ба мо лозим аст индексҳои ва -ро ёбем, ки
ва қимати то ҳадди имкон калон бошад.
Биёед сарҳади чап -ро собит кунем ва сарҳади рости максималӣ -ро ёбем, ки
Ин қиматро бо ишора мекунем.
Пас ҷавоби масъала чунин аст:
Ҳалли мустақим ин аст, ки ҳар як сарҳади чапро ҷудогона санҷем ва сарҳади ростро то ҳадди имкон дароз кунем.
Инро метавон дар татбиқ кард:
Ин кор мекунад, аммо барои -и калон хеле суст аст.
Мушоҳидаи калидӣ ин аст:
Мушоҳида 1. барои ҳамаи .
Ин маъно дорад, ки агар мо сарҳади чапро ба рост ҷунбонем, беҳтарин сарҳади рости имконпазир ҳеҷ гоҳ ба қафо намеравад.
Пас ба ҷои аз нав оғоз кардани ҷустуҷӯ барои ҳар як , мо метавонем нишондиҳандаи ростро дар ҷояш нигоҳ дорем ва танҳо ба пеш ҳаракат диҳем.
Маҳз ҳамин чиз техникаи ду нишондиҳандаро самаранок мекунад.
Мо ду нишондиҳандаро нигоҳ медорем:
i = сарҳади чапи порчаи ҷорӣj = сарҳади рости порчаи ҷорӣҲамчунин ҷамъбасти ҷории порчаи -ро нигоҳ медорем.
Барои ҳар мавқеи i, мо j-ро то ҳадди имкон ба рост мебарем, то даме ки ҷамъбаст аз зиёд нашавад. Сипас opt[i] = j-ро сабт мекунем.
Пеш аз гузаштан ба i-и навбатӣ, мо a[i]-ро аз ҷамъбасти ҷорӣ хориҷ мекунем.
Азбаски ҳар як нишондиҳанда танҳо ба пеш ҳаракат мекунад, шумораи умумии ҳаракатҳо барои ҳар нишондиҳанда ҳадди аксар аст, ва мураккабии вақтӣ мешавад.
Бигзор
Мо бо i = 1, j = 0, sum = 0 оғоз мекунем.
j-ро то ҳадди имкон дароз мекунем:
2-ро илова мекунем sum = 21-ро илова мекунем sum = 33-ро илова карда наметавонем, зеро sum ба 6 мерасадПас opt[1] = 2, ва порча аст.
Ҳоло i-ро ба 2 мебарем:
a[1] = 2-ро хориҷ мекунем, пас sum = 1j-ро дароз кунем:
3-ро илова мекунем sum = 42-ро илова карда наметавонем, зеро sum ба 6 мерасадПас opt[2] = 3, ва порча аст.
Бо ҳамин тарз идома дода, мо беҳтарин порчаи иҷозатдодашударо меёбем.
Масъала: Массиви тартибдодашудаи дода шудааст, шумораи ҷуфтҳои -ро ҳисоб кунед, ки ва .
Идея: Аз ду канор ду нишондиҳанда истифода баред. Агар бошад, пас ҳамаи ҷуфтҳои дурустанд, бинобар ин мо -ро илова мекунем ва l-ро ҷунбонем. Дар акси ҳол, r-ро ҷунбонем.
Масъала: Ду массиви тартибдодашудаи ва дода шудаанд, ҳамаи унсурҳоро бо тартиби афзоянда бароред.
Идея: Дар ҳар массив як нишондиҳанда нигоҳ доред. Дар ҳар қадам, унсурҳои ҷориро муқоиса кунед ва хурдтаринашро гиред.
Масъала: Сатри ва намунаи дода шудаанд, хурдтарин зерсатри -ро ёбед, ки ҳамаи аломатҳои -ро дар бар мегирад.
Идея: Нишондиҳандаи ростро васеъ кунед, то даме ки тирезаи ҷорӣ ҳамаи аломатҳои лозимаро дар бар гирад. Сипас нишондиҳандаи чапро ҷунбонед, то тиреза то ҳадди имкон хурд шавад.
// i: индекси чапи интервали ҷорӣ
// j: индекси рости интервали ҷорӣ
// (максималии r, ки sum <= K)
for (int i = 1; i <= n; i++) {
int j = i - 1;
int sum = 0;
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
}
for (int i = 1, j = 0, sum = 0; i <= n; i++) {
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
sum -= a[i];
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
cin >> n >> K;
vector<int> a(n + 1), opt(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int j = 0;
int sum = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
while (j + 1 <= n && sum + a[j + 1] <= K) {
j++;
sum += a[j];
}
opt[i] = j;
ans = max(ans, opt[i] - i + 1);
sum -= a[i];
}
cout << ans << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, K;
cin >> n >> K;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
long long ans = 0;
int l = 0, r = n - 1;
while (l < r) {
if (a[l] + a[r] <= K) {
ans += (r - l);
l++;
} else {
r--;
}
}
cout << ans << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> A(n), B(m);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
for (int j = 0; j < m; j++) {
cin >> B[j];
}
int i = 0, j = 0;
vector<int> merged;
while (i < n && j < m) {
if (A[i] < B[j]) {
merged.push_back(A[i++]);
} else {
merged.push_back(B[j++]);
}
}
while (i < n) {
merged.push_back(A[i++]);
}
while (j < m) {
merged.push_back(B[j++]);
}
for (int x : merged) {
cout << x << " ";
}
cout << "\n";
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, p;
cin >> s >> p;
vector<int> need(256, 0), have(256, 0);
for (char c : p) {
need[c]++;
}
int required = p.size();
int l = 0, formed = 0, best_len = 1e9, best_l = 0;
for (int r = 0; r < (int)s.size(); r++) {
char c = s[r];
have[c]++;
if (need[c] > 0 && have[c] <= need[c]) {
formed++;
}
while (formed == required) {
if (r - l + 1 < best_len) {
best_len = r - l + 1;
best_l = l;
}
have[s[l]]--;
if (need[s[l]] > 0 && have[s[l]] < need[s[l]]) {
formed--;
}
l++;
}
}
if (best_len == 1e9) {
cout << "-1\n";
} else {
cout << s.substr(best_l, best_len) << "\n";
}
return 0;
}