Submission

Score: 0

User: Cmoss9

Problemset: ห้องสมุดเมือง 3M

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-18 22:00:01

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; // จำนวนห้องสมุด
    cin >> n;

    vector<pair<int, int>> ranges(n);
    int max_val = 0; // ค่ามากสุดที่พบในช่วง
    int total_books = 0; // จำนวนหนังสือทั้งหมด

    // รับข้อมูลช่วง Xi และ Yi ของแต่ละห้องสมุด
    for (int i = 0; i < n; i++) {
        cin >> ranges[i].first >> ranges[i].second;
        total_books += (ranges[i].second - ranges[i].first); // คำนวณจำนวนหนังสือทั้งหมด
        max_val = max(max_val, ranges[i].second); // หาค่ามากสุดในช่วง
    }

    // ใช้ vector เพื่อเก็บจำนวนหนังสือในแต่ละจำนวนตัวอักษร
    vector<int> freq(max_val + 1, 0);

    // เพิ่มความถี่ในอาร์เรย์สำหรับแต่ละช่วง
    for (int i = 0; i < n; i++) {
        for (int j = ranges[i].first; j < ranges[i].second; j++) {
            freq[j]++;
        }
    }

    // คำนวณตำแหน่งของค่ามัธยฐาน (ตำแหน่งที่ K / 2)
    int half = total_books / 2;
    int accumulated = 0;
    int median = -1;

    // ถ้าจำนวนข้อมูลทั้งหมดเป็นเลขคู่
    if (total_books % 2 == 0) {
        int first_middle = -1, second_middle = -1;

        // หา 2 ค่าที่อยู่กลาง
        for (int i = 0; i <= max_val; i++) {
            accumulated += freq[i];

            if (accumulated >= half && first_middle == -1) {
                first_middle = i;
            }

            if (accumulated > half) {
                second_middle = i;
                break;
            }
        }

        // คำนวณค่ามัธยฐานจากค่า 2 ค่า
        median = (first_middle + second_middle) / 2;
    } else {
        // ถ้าจำนวนข้อมูลทั้งหมดเป็นเลขคี่
        for (int i = 0; i <= max_val; i++) {
            accumulated += freq[i];
            if (accumulated >= half) {
                median = i;
                break;
            }
        }
    }

    // แสดงผลค่ามัธยฐาน
    cout << median << endl;

    return 0;
}