Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
1.3 kB
2
Indexable
Never
long solution(int n, long c, int d, int[] arr) {
        Arrays.sort(arr);

        int low = 0;
        int high = d;
        long result = -1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (canAchieveTarget(n, c, d, arr, mid)) {
                result = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return result;
    }

    public static boolean canAchieveTarget(int n, long c, int d, int[] arr, int k) {
        long skillPoints = 0;
        int[] cooldown = new int[n];
        Arrays.fill(cooldown, Integer.MIN_VALUE / 2); // fill with large negative values to simulate exercises not used initially

        for (int day = 0; day < d; day++) {
            int bestGain = 0;
            int bestExercise = -1;

            for (int i = 0; i < n; i++) {
                if (day - cooldown[i] > k && arr[i] > bestGain) {
                    bestGain = arr[i];
                    bestExercise = i;
                }
            }

            if (bestExercise != -1) {
                cooldown[bestExercise] = day;
                skillPoints += bestGain;
            }

            if (skillPoints >= c) {
                return true;
            }
        }

        return skillPoints >= c;
    }
Leave a Comment