BOJ 13904チャレンジ

12167 ワード
2021.05.09 テキストリンク
https://www.acmicpc.net/problem/13904
1秒、256 MBメモリ
input :
  • N (1 ≤ N ≤ 1,000)
  • d(1≦d≦1000)w(1≦w≦100)[dは課題締切日までの残り日数wは課題の点数]
    • output :
  • 出力点数の最低価格
    • 条件:
  • 1日に1つのタスクを完了することができ、各タスクには締め切りがあり、すべてのタスクを完了できない可能性があります.
  • 締め切りを過ぎた作業では得点できない.
    • 毎日、私は何をすべきか考えていますが、毎日最大の値を選択すると、別の値を逃す可能性があります.
    他の方法では,一日が過ぎるのではなく,現在から締め切りまでの課題提出計画を立てることが望ましい.
    課題の締め切りまでの残り日数のうち、最大値は1000です.
    1000の案を作成し、日付ごとに行う課題に点数をつけます.
    そして最後にこの値を加えます.
    例.
    7
    4 60
    4 40
    1 20
    2 50
    3 30
    4 10
    6 5
    これを点数の降順で並べ替えた後.
    個々の値を実行する日付があるかどうかを決定します.自分がやるべき日付に他の課題がある場合は、日付-1の確認を行う際に、その値が-1である0より小さい場合は放棄する.
    歯を食いしばる.
    そして真ん中はdata[cnt]!=0を条件としてハングアップし、エラーが発生したため、エラーを防止するためにcnt>=0を先にハングアップします.
    このように,演算子の優先度のため,先に前の値を判別する必要はない.
    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Problem implements Comparable<Problem>{
    int day, score;

    public Problem(int day, int score){
        this.day = day;
        this.score = score;
    }

    @Override
    public int compareTo(Problem o){
        return o.score - this.score;
    }
}

public class BOJ_13904_assignment {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] data = new int[1000];
    static ArrayList<Problem> problem = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++){
            String[] temp = br.readLine().split(" ");
            problem.add(new Problem(Integer.parseInt(temp[0]), Integer.parseInt(temp[1])));
        }

        Collections.sort(problem);
        for (Problem item : problem){

            int cnt = item.day - 1;
            while (cnt >= 0 && data[cnt] != 0) {
                cnt--;
            }

            if (cnt < 0)
                continue;

            data[cnt] = item.score;
        }

        int sum = 0;
        for (Integer item : data)
            sum += item;

        System.out.println(sum);
    }
}
    [SS]継承
    Maximum Subarray