수학적 분석

이 문제의 중요한 성질은 다음과 같습니다: 만약 \(0<a<b<c<d\)라면, \((a-d)^2+(b-c)^2 > (a-c)^2+(b-d)^2\)

증명:

1. 두 식을 각각 1식과 2식으로 설정합니다.
2. \((a-d)^2+(b-c)^2 = a^2+b^2+c^2+d^2-2ad-2bc\), \((a-c)^2+(b-d)^2 = a^2+b^2+c^2+d^2-2ac-2bd\)
3. \(a*(c-d) > b*(c-d)\)이므로, \(-2ad-2bc > -2ac-2bd\)
4. 따라서 \(a^2+b^2+c^2+d^2-2ad-2bc>a^2+b^2+c^2+d^2-2ac-2bd\)이고, 이에 따라 \((a-d)^2+(b-c)^2 > (a-c)^2+(b-d)^2\)

완전 탐색 → 이진 탐색

완전 탐색 방식은 간단히 구현할 수 있습니다. 경계를 넓힐 때마다 정렬하고 검증 값이 T보다 커질 때까지 반복합니다. 그러나 최악의 경우 시간 복잡도는 \(O(n^3 log n)\)으로 매우 비효율적입니다.

모든 숫자가 음이 아닌 정수이므로, 오른쪽 경계가 확장될 때 검증 값은 항상 증가합니다. 이를 이용하여 이진 탐색을 적용할 수 있습니다.

시간 복잡도 계산

이론적으로 완전 탐색과 동일한 복잡도로 계산하면 \(O(n^2 log^2n)\)이 됩니다. 이 역시 비효율적이지만, 약간의 오차로 인해 40점 정도를 얻을 수 있습니다.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 500010;
int n, m, k;
int arr[MAXN];

int temp[MAXN];
bool verify(int left, int right) {
    int len = 0;
    for(int i = left; i <= right; i++) temp[len++] = arr[i];
    sort(temp, temp + len);

    long long result = 0;
    for(int i = 0; i < m && i < len; i++, len--) 
        result += (temp[i] - temp[len - 1]) * (temp[i] - temp[len - 1]);

    return result > k;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int testCases; cin >> testCases;
    while(testCases--) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; i++) cin >> arr[i];

        int start = 0, count = 0;
        while(start < n) {
            int left = start, right = n;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(verify(start, mid)) right = mid;
                else left = mid + 1;
            }
            start = right;
            count++;
        }
        cout << count << endl;
    }

    return 0;
}

이진 탐색 → 배수 증가법

배수 증가법은 남은 구간에서 적합한 오른쪽 경계를 찾는데 \(O(log(len_i))\)의 시간 복잡도를 사용합니다. 이 방법의 최악의 경우 시간 복잡도는 \(O(nlog^2n)\)이며, 점수가 90점 정도입니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 500010;
ll n, m, k;
int arr[MAXN];

ll temp[MAXN];
ll compute(int left, int right) {
    int len = 0;
    for(int i = left; i <= right; i++) temp[len++] = arr[i];
    sort(temp, temp + len);

    ll result = 0;
    for(int i = 0; i < m && i < len; i++, len--) 
        result += (temp[i] - temp[len - 1]) * (temp[i] - temp[len - 1]);

    return result;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int testCases; cin >> testCases;
    while(testCases--) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; i++) cin >> arr[i];

        int start = 0, end = 0, count = 0;
        while(end < n) {
            int len = 1;
            while(len) {
                if(end + len <= n && compute(start, end + len - 1) <= k) 
                    end += len, len <<= 1;
                else len >>= 1;
            }
            start = end;
            count++;
        }
        cout << count << endl;
    }

    return 0;
}

배수 증가법 + 2-way 병합 정렬

배수 증가법을 사용하여 새로운 구간을 추가할 때, 이미 정렬된 구간과 새로 추가된 구간을 병합하여 전체 정렬을 피할 수 있습니다. 이 방법의 시간 복잡도는 최적의 \(O(nlogn)\)입니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 500010;
ll n, m, k;
ll arr[MAXN];

ll temp1[MAXN], temp2[MAXN];
ll calc(int left, int mid, int right) {
    for(int i = mid; i < right; i++) temp1[i] = arr[i];
    int i = left, j = mid, len = 0;
    sort(temp1 + mid, temp1 + right);

    while(i < mid && j < right) 
        temp2[len++] = (temp1[i] <= temp1[j]) ? temp1[i++] : temp1[j++];
    while(i < mid) temp2[len++] = temp1[i++];
    while(j < right) temp2[len++] = temp1[j++];

    ll result = 0;
    for(int i = 0; i < m && i < len; i++, len--) 
        result += (temp2[i] - temp2[len - 1]) * (temp2[i] - temp2[len - 1]);

    return result;
}

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int testCases; cin >> testCases;
    while(testCases--) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; i++) cin >> arr[i];

        int start = 0, end = 0, count = 0;
        while(end < n) {
            int len = 1;
            while(len) {
                if(end + len <= n && calc(start, end, end + len) <= k) {
                    end += len, len <<= 1;
                    if(end == n) break;
                    for(int i = start; i < end; i++) temp1[i] = temp2[i - start];
                } else len >>= 1;
            }
            start = end;
            count++;
        }
        cout << count << endl;
    }

    return 0;
}