CSP 202303-2 垦田计划

黎 浩然/ 16 8 月, 2023/ 算法/ALGORITHMS/ 0 comments

Java：100/100

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long m = input.nextInt();
        int k = input.nextInt();
        int [] t = new int[n];
        int [] c = new int[n];

        for (int i = 0; i < n; i++) {
            t[i] = input.nextInt();
            c[i] = input.nextInt();
        }

        Integer [] indexArray = new Integer[n];
        for (int i = 0; i < n; i++) {
            indexArray[i] = i;
        }
        Arrays.sort(indexArray, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(t[o2], t[o1]);
            }
        });

        int [] sortedT = new int[n];
        int [] sortedC = new int[n];
        for (int i = 0; i < n; i++) {
            sortedT[i] = t[indexArray[i]];
            sortedC[i] = c[indexArray[i]];
        }

        int cost2Minus1 = 0;
        for (int i = 0; i < n; i++) {
            if (sortedT[i] <= k) {
                System.out.println(k);
                System.exit(0);
            }

            int nextDay = k;
            if (i + 1 < n) {
                nextDay = Math.max(sortedT[i + 1], k);
            }

            cost2Minus1 += sortedC[i];

            for (int j = 0; j < sortedT[i] - nextDay; j++) {
                if (m < cost2Minus1) {
                    System.out.println(sortedT[i] - j);
                    System.exit(0);
                }
                m -= cost2Minus1;
            }
        }

        System.out.println(k);
    }
}