Ikki ko‘rsatkich usuli
Ikki ko‘rsatkich usuli qanday ishlashini o‘rganing
Kirish
Faraz qilaylik, bizga massivi va soni berilgan. Biz elementlari yig‘indisi dan oshmaydigan maksimal uzunlikdagi ostmassivini topmoqchimiz.
Ikki ko‘rsatkich usuli qanday ishlashini o‘rganing
Faraz qilaylik, bizga massivi va soni berilgan. Biz elementlari yig‘indisi dan oshmaydigan maksimal uzunlikdagi ostmassivini topmoqchimiz.
Boshqacha aytganda, va indekslarini shunday topishimiz kerakki,
va qiymati imkon qadar katta bo‘lsin.
Keling, chap chegara ni fiksatsiya qilaylik va quyidagi shart bajariladigan maksimal o‘ng chegara ni topaylik:
Bu qiymatni deb belgilaymiz.
Unda masalaning javobi
Oddiy yechim — har bir chap chegarani alohida sinab ko‘rish va o‘ng chegarani imkon qadar uzoqqa cho‘zish.
Buni da amalga oshirish mumkin:
Bu ishlaydi, ammo katta uchun juda sekin.
Asosiy kuzatuv:
Kuzatuv 1. Barcha uchun .
Bu shuni anglatadiki, agar chap chegarani o‘ngga sursak, eng yaxshi mumkin bo‘lgan o‘ng chegara hech qachon orqaga qaytmaydi.
Shuning uchun har bir uchun qidiruvni qaytadan boshlash o‘rniga, o‘ng ko‘rsatkichni o‘sha joyida qoldirib, uni faqat oldinga siljitishda davom etishimiz mumkin.
Aynan shu narsa ikki ko‘rsatkich (two pointers) texnikasini samarali qiladi.
Biz ikkita ko‘rsatkichni saqlaymiz:
i = joriy segmentning chap chegarasij = joriy segmentning o‘ng chegarasiShuningdek, segmentining joriy yig‘indisini saqlaymiz.
Har bir i pozitsiya uchun, yig‘indi dan oshmaydigan bo‘lib turgan paytda j ni imkon qadar o‘ngga siljitamiz. So‘ng opt[i] = j ni yozib qo‘yamiz.
Keyingi i ga o‘tishdan oldin, joriy yig‘indidan a[i] ni olib tashlaymiz.
Har bir ko‘rsatkich faqat oldinga siljigani uchun, umumiy siljishlar soni har bir ko‘rsatkich uchun ko‘pi bilan bo‘ladi, vaqt murakkabligi .
Quyidagini olaylik
Biz i = 1, j = 0, sum = 0 dan boshlaymiz.
j ni kengaytiramiz:
2 ni qo‘shamiz sum = 21 ni qo‘shamiz sum = 33 ni qo‘sha olmaymiz, chunki sum 6 bo‘lib qoladiDemak opt[1] = 2, segment esa .
Endi i ni 2 ga o‘tkazamiz:
a[1] = 2 ni olib tashlaymiz, demak sum = 1j ni kengaytira olamiz:
3 ni qo‘shamiz sum = 42 ni qo‘sha olmaymiz, chunki sum 6 bo‘lib qoladiDemak opt[2] = 3, segment esa .
Shu tarzda davom etib, eng yaxshi yaroqli segmentni topamiz.
Masala: Saralangan massiv berilgan. va bo‘ladigan juftliklar sonini hisoblang.
G‘oya: Qarama-qarshi uchlardan ikki ko‘rsatkichdan foydalaning. Agar bo‘lsa, unda juftliklarning barchasi yaroqli, shuning uchun ni qo‘shamiz va l ni siljitamiz. Aks holda, r ni siljitamiz.
Masala: Ikki saralangan va massiv berilgan, barcha elementlarni saralangan tartibda chiqaring.
G‘oya: Har bir massivda bittadan ko‘rsatkichni ushlab turing. Har qadamda joriy elementlarni solishtirib, kichigini oling.
Masala: satr va andoza berilgan. ning barcha belgilarini o‘z ichiga oladigan ning eng kichik ostsatrini toping.
G‘oya: Joriy oyna barcha kerakli belgilarni o‘z ichiga olguncha o‘ng ko‘rsatkichni kengaytiring. So‘ng oynani imkon qadar kichik qilish uchun chap ko‘rsatkichni siljiting.
// i: joriy intervalning chap indeksi
// j: joriy intervalning o‘ng indeksi
// (sum <= K bo‘ladigan maksimal r)
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;
}