제출 #1330346

#제출 시각아이디문제언어결과실행 시간메모리
1330346bradley0927Just Long Neckties 2 (JOI25_ho_t4)C++20
0 / 100
1 ms344 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Just Odd Inventions (JOI)
 * Complexity: O(N + max(Ai))
 */

int main() {
    // Crucial for 5 million inputs
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    // Use a frequency array since Ai is very small (1 to 21)
    vector<int> freq(22, 0);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a <= 21) freq[a]++;
    }

    int max_k = 0;
    int count_le_v = 0;

    // Iterate through all possible necktie lengths v
    for (int v = 1; v <= 21; v++) {
        count_le_v += freq[v];
        
        // From the logic: count_le_v <= k * v + (k - 1)
        // count_le_v <= k * (v + 1) - 1
        // count_le_v + 1 <= k * (v + 1)
        // k >= (count_le_v + 1) / (v + 1)
        
        int required_k = (count_le_v + 1 + v) / (v + 1); 
        // Note: (a + b - 1) / b is the formula for ceil(a/b)
        // Here: ceil((count_le_v + 1) / (v + 1))
        
        if (required_k > max_k) {
            max_k = required_k;
        }
    }

    // The minimum k is 1, even if the math says 0
    cout << max(1, max_k) << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...