Two Pointers

توضیحات

Two Pointers

در روش two pointers دو نشانگر بر روی یک آرایه پیمایش داده میشوند.
هر دو نشانگر یکنواخت میباشند؛ یعنی هر نشانگر از یک نقطه از آرایه شروع به حرکت میکند و یک نقطه به پایان میرسد و فقط در یک جهت حرکت میکند.

مسئله

یک ارایه \(a_{1}, a_{2}, \dots, a_{n}\) \((1 \leq a_i \leq T)\) به طول \(n\) \((1 \leq n \leq 10^{6})\) و یک عدد \(T\) داریم، به ازای هر \(i\) میخواهیم بیشینه \(j\) ای را بیابیم به طوری که \(\sum_{k=i}^j a_k \leq T\).

راه حل

فرض کنید \(f_i\) بیشینه عددی باشد که \(\sum_{k=i}^{f_i} a_k \leq T\) در این صورت ادعا میکنیم:

\[\forall \quad i < j \Longrightarrow f_i \leq f_j \]

اثبات

برهان خلف میزنیم:

\[ \exists \quad i < j: f_i > f_j \]

\[1) \sum_{k=j}^{f_j+1} a_k > T \]

\[ 2) \sum_{k=i}^{j-1} a_k + \sum_{k=j}^{f_j+1} a_k + \sum_{k=f_j+2}^{f_i} a_k \leq T \rightarrow \sum_{k=j}^{f_j+1} a_k \leq T \]

که با توجه به نتایج بدست امده از نتیجه \(1\) و نتیجه \(2\) به تناقض رسیده. دقت کنید از آنجایی که اعداد آرایه مثبت بودند، هر کدام از سیگما‌ها هم نامنفی خواهند بود.

با توجه به ادعا گفته شده میتوان نتیجه گرفت:

\[ f_1 \leq f_2 \leq \dots \leq f_n \]

حال کافیست یک نشانگر(pointer) داشته باشیم که روی آرایه پیمایش کند (\(ptri\)) و یک نشانگر دیگر (\(ptrj\)) به طوری که شرط \(ptrj \leq f_{ptri}\) همواره برقرار بماند.

و به ازای هر مقدار \(ptri\) مقدار \(ptrj\) را تاجای ممکن افزایش دهیم.

توجه کنید که با توجه به لم گفته شده با افزایش \(ptri\) مقدار \(ptrj\) کاهش نمیابد.

کد

int main(){
    int n; cin >> n;
    long long T; cin >> T;
    vector<int> a(n);
    for(int i = 0; i < n; i++) 
        cin >> a[i];

    int ptri = 0, ptrj = -1;
    long long sum = 0; // (1)!

    while(ptri < n){
        while(ptrj < n-1 && sum + a[ptrj + 1] <= T) { // (2)!
            ptrj++;
            sum += a[ptrj];
        }
        cout << ptrj + 1 << ' '; // (3)!
        sum -= a[ptri]; // (4)!
        ptri++;
    }
}

1. \(sum = \sum_{k=ptri}^{ptrj} a_k\)

2. \(ptrj\) را تا جای ممکن افزایش میدهیم

3. خروجی را به صورت یک بیس نشان میدهیم

4. برای افزایش \(ptri\) مقدار \(sum\) را به روز رسانی میکنیم

پیچیدگی زمانی

با توجه به این که دو نشانگرمان همواره افزایش میابند و هیچگاه بیشتر از \(n\) نخواهند شد، و از انجایی که به ازای افزایش هر یک \(O(1)\) هزینه میکنیم، پس اردر کل‌مان برابر \(O(n)\) میشود.

منابع بیشتر:

• Codeforces Edu
• 8.1 - Two Pointers

سوال ها

نیاز به عضویت در گروه شاززز!

برای حل برخی از سوالات باید ابتدا در گروه شاززز عضو شوید.

سوال	سختی	تگ ها	جاج
Sum of Three Values	800	Spoiler Two Pointers	CSES
Born this way	1200	Spoiler Two Pointers	Codeforces
A Tale of Two Lands	1200	Spoiler Two Pointers	Codeforces
Mysterious Crime	1500	Spoiler Two Pointers	Codeforces
رژیم جسی	1500	Spoiler Two Pointers	Shaazzz
Same Count One	1600	Spoiler Two Pointers	Codeforces
Binary String	1600	Spoiler Two Pointers	Codeforces
Longest k-Good Segment	1600	Spoiler Two Pointers	Codeforces
Remove the Substring (hard version)	1700	Spoiler Two Pointers	Codeforces
Xenia and Colorful Gems	1700	Spoiler Two Pointers	Codeforces
Read Time	1900	Spoiler باینری سرچ Two Pointers	Codeforces
Minimizing Difference	2000	Spoiler باینری سرچ Two Pointers الگوریتم های حریصانه	Codeforces
Double Knapsack	3000	Spoiler Two Pointers پریفیکس سام	Codeforces
I Might Be Wrong	3400	Spoiler Two Pointers	Codeforces

نظرات