จำนวนคู่เพื่อนน้อยที่สุดและมากที่สุดในทีม C++

ปัญหา

มีผู้เข้าร่วม n คน แบ่งเป็น m ทีม (แต่ละทีมอย่างน้อย 1 คน) หลังการแข่งขัน สมาชิกในทีมเดียวกันจะกลายเป็นเพื่อนกันหมด หาจำนวนคู่เพื่อนที่น้อยที่สุดและมากที่สุดที่เป็นไปได้

การวิเคราะห์

จำนวนคู่ในทีมที่มีขนาด k คือ C(k,2) = k(k-1)/2

จำนวนคู่สูงสุด (Max Pairs)

ทำให้ทีมหนึ่งใหญ่ที่สุดเท่าที่จะเป็นไปได้ ทีมอื่นขนาด 1

• ทีมใหญ่: n-m+1 คน
• ทีมอื่น: m-1 ทีม ขนาด 1 คน (ไม่มีคู่)
• Max pairs = (n-m+1)(n-m)/2

จำนวนคู่น้อยที่สุด (Min Pairs)

กระจายคนให้เท่าเทียมที่สุด

• q = n/m (ขนาดทีมพื้นฐาน)
• r = n % m (ทีมที่ได้คนเพิ่ม 1 คน)
• มี r ทีมขนาด q+1, และ m-r ทีมขนาด q
• Min pairs = r × C(q+1,2) + (m-r) × C(q,2)

ตัวอย่างโค้ด C++

#include <iostream>
#include <cmath>
using namespace std;

void getMinMaxPairs(int n, int m) {
    // Max pairs: ทีมใหญ่สุดขนาด n-m+1
    long long maxPairs = 1LL * (n - m + 1) * (n - m) / 2;
    
    // Min pairs: แบ่งเท่าๆ กัน
    long long q = n / m;      // ขนาดพื้นฐาน
    long long r = n % m;      // จำนวนทีมที่ได้คนเพิ่ม
    
    long long minPairs = r * (q + 1) * q / 2 + (m - r) * q * (q - 1) / 2;
    
    cout << "Minimum pairs = " << minPairs << endl;
    cout << "Maximum pairs = " << maxPairs << endl;
}

int main() {
    // ตัวอย่าง
    getMinMaxPairs(5, 2); // n=5, m=2
    // Min: ทีม 3+2 → 3+1=4 pairs
    // Max: ทีม 4+1 → 6+0=6 pairs
    
    cout << "---" << endl;
    getMinMaxPairs(10, 3);
    return 0;
}

ผลลัพธ์

Minimum pairs = 4
Maximum pairs = 6
---
Minimum pairs = 15
Maximum pairs = 28

การตรวจสอบ n=5, m=2

• Min: ทีม 3 คน (3 คู่) + ทีม 2 คน (1 คู่) = 4 คู่
• Max: ทีม 4 คน (6 คู่) + ทีม 1 คน (0 คู่) = 6 คู่