คำอธิบายวิธีทำพร้อม code สำหรับข้อ toi13_cats

Author: $kaopj$

Problem

สรุปโจทย์

มีแมว $N$ ตัว ($N$ เป็นจำนวนคู่) โดยที่

แมวมีขนาดเป็นจำนวนเต็ม
แมวทุกตัวมีคู่เสมอ
แมวที่เป็นคู่กันมีขนาดเท่ากันและไม่มีขนาดเท่ากับแมวคู่อื่นๆ

โดยที่เราอยากให้แมวที่เป็นคู่กันอยู่ติดกัน

แต่ว่ารูปแบบแมวที่ให้มาอาจจะไม่อยู่ติดกับคู่ของมันได้ ดังนั้นเราจึงมีกรงอันหนึ่งเอาไว้เคลื่อนย้ายแมว โดยที่ 1. เราจะมีกรงเดียว 2. กรงขนาด $c$ จะใส่แมวที่มีขนาดที่น้อยกว่าหรือเท่ากับ $s$ ได้เท่านั้น(สมมติว่าขนาดของกรงคือ $c$) 3. กรงใส่แมวได้อย่างมาก $1$ ตัว

เราอยากได้ว่าขนาดกรงที่น้อยที่สุดเท่าที่เป็นไปได้คือเท่าไหร่

ตัวอย่าง

สมมติให้มีแมวทั้งสิ้น $6$ ตัว ($N=6$) ดังรูป

example1

เห็นได้ชัดว่าคู่แมวที่มีขนาดเป็น $2$ ไม่ได้อยู่ติดกัน ส่วนคู่แมวที่เหลืออยู่ติดกัน ดังนั้นขนาดกรงที่น้อยที่สุดที่เป็นไปได้คือ $2$

example2

สิ่งที่ต้องทำ

เขียนโค้ดที่จะหาว่าขนาดกรงที่น้อยที่สุดเท่าที่จะเป็นไปได้คือเท่าไหร่

Constraints

$N$ หมายถึง จํานวนแมวทั้งหมด และ $2\leq N\leq 2,000,000$
$s_i$ หมายถึง ขนาดของแมวตัวที่ $i$ และ $1\leq s_i \leq 2^{31}$

Prerequisites

Brute Force
Binary Search

Solution

ข้อสังเกต

ถ้าเรานิยาม $f(x)$ เป็นดังนี้

\[f(x)=\begin{cases} 1; \text{สามารถใช้กรงขนาด $x$ ในการเคลื่อนย้ายแมว เพื่อให้แมวที่เป็นคู่กันอยู่ติดกัน}\\ 0; \text{ไม่สามารถใช้กรงขนาด $x$ ในการเคลื่อนย้ายแมว เพื่อให้แมวที่เป็นคู่กันอยู่ติดกัน} \end{cases}\]

สังเกตได้ว่า 1. ถ้า $f(x)=1$ จะได้ว่าสำหรับทุกๆ $y\geq x$ จะได้ $f(y)=1$ 2. ถ้า $f(x)=0$ จะได้ว่าสำหรับทุกๆ $y\leq x$ จะได้ $f(y)=0$

ดังนั้นเราสามารถใช้ Binary Search on Answer เพื่อหาขนาดกรงที่น้อยที่สุดได้

วิธีทำ

สำหรับการคำนวนหาค่า $f(x)$ เราสามารถใช้การ Brute Force ได้โดยที่เราไม่ต้องสนใจแมวที่มีขนาดน้อยกว่าหรือเท่ากับ $x$ เลยเพราะเราสามารถเคลื่อนย้ายมันได้ เราแค่ต้องเช็คว่า คู่แมวที่มีขนาดมากกว่า $x$ อยู่ติดกันทุกคู่หรือไม่

วิธีการตรวจสอบว่า คู่แมวที่มีขนาดมากกว่า $x$ อยู่ติดกันทุกคู่หรือไม่ (หาค่า f(x))

สร้างตัวแปร $lastcat$ เพื่อคอยเก็บว่า แมวที่ขนาด $>x$ ตัวล่าสุดที่พบ มีขนาดเท่าไหร่
loop ตามแมวแต่ละตัว ตั้งแต่ $1$ -> $N$
ถ้าขนาดแมว $\leq x$ ก็ข้ามได้เลย (พิจารณาแค่กรณีที่ขนาดแมว $> x$)
ถ้าขนาดแมว $ > x$ ก็พิจารณาแยกกรณี ดังนี้:
- ถ้า $lastcat == -1$ แสดงว่า ตัวที่จับคู่ก่อนหน้านี้ ถูกจับคู่ไปครบแล้ว และนี่เป็นการตามหาคู่แมวใหม่
- ถ้า $lastcat ==$ ขนาดของแมวตัวปัจจุบัน แสดงว่า ในระหว่างคู่แมวที่มีขนาดตัวเท่ากัน ไม่มีแมวขนาดใหญ่กว่า $x$ ตัวอื่นคั่นไว้ ก็ตั้ง $lastcat$ เป็น $-1$ เหมือนเดิม
- ถ้า $lastcat \neq$ ขนาดของแมวตัวปัจจุบัน แสดงว่า มีแมวขนาด $> x$ ที่คั่นอยู่ ก็คืนค่า 0 ได้เลย

โดยที่เราจะใช้ Binary Search on answer โดยที่กำหนดค่า $l=1,r=2^31$ โดยให้ $mid=\frac{l+r}{2}$ และทำคำสั่งนี้ไปเรื่อยๆจนกว่า $l>r$ 1. ถ้า $f(mid)=1$ ให้ $r=mid-1$ 2. ถ้า $f(mid)=0$ ให้ $l=mid+1$

คำตอบจะเป็นค่า $l$ ที่ได้ออกมา

Code

toi13_cats.cpp

#include <bits/stdc++.h> 

#define int long long 

using namespace std; 
const int MAXN=2e6;
int N;
int s[MAXN+1];
int f(int x) {
    int lastcat=-1;
    for (int i=1;i<=N;i++) {
        if (s[i]>x) {
            if (lastcat==-1) {
                lastcat=s[i]; // new pair
            } else if (lastcat==s[i]) {
                lastcat=-1; // we found the pair for lastcat
            } else {
                return 0; // lastcat != s[i] so the pairs arent adjacent
            }
        }
    }
    return 1;
}
int32_t main(){ 
    cin >> N;
    for (int i=1;i<=N;i++) {
        cin >> s[i];
    }
    int l=1,r=(1ll<<31),mid; // (1ll<<31) is 2^31
    while (l<=r) {
        mid=(l+r)/2;
        if (f(mid)==1) {
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    cout << l;
}

Total Time Complexity

หาค่า $f(x)$ ใช้เวลา $O(N)$ ต้องหาค่า $f(x)$ $O(\log(\max(s_i)))$ ครั้ง Total: $O(N\log(\max(s_i)))$