百俊カップ麺(1781)

カップラーメン

1.ヒント

1)dddであれば[1]、d][1,d][1,d][1,d]日以内にこの問題を解決できる.

2)まず簡単な問題を見て、どの問題を選ぶかを決めます。ある問題を確認し、dddと呼びます。しかし、もしあなたが今解決している問題がddd個未満であれば、あなたはいつもその問題を解決することができます。

3)もちろん,上記の問題は必ずしも最良ではない.短い問題からプレゼンテーションを開始すると、選択した問題をいつでも新しい問題に置き換えることができます。

2.近接

似たような問題を解いたことがありますか。

巡回講演
まったく同じ問題(範囲を除く).巡回講演問題はO(N 2)O(N^2)O(N 2)O(N 2)O(N 2)でもよいが,この問題NNNは最大2×1052\times 10^52×105なので無理です.

簡単な方法から始められますか?

一見、dddごとにもらえるカップ麺の数は最高のvvvから選べばいいです.しかし、ddd日に問題を解決する必要はないので、これは不可能です.

3
3 3
3 2
3 1

1と入力すると、 2, 31,\2,\31, 2, 3日目に分けてやればすべての問題ができる

順序を強制できますか?

Dedrain短い質問は時間があれば入れておきましょうもちろん、誤った選択をする可能性がありますが、既存の選択を挽回することができます.
現在確認している問題に比べて、既存の問題の分機は無条件に同じか短いため、現在確認している問題に置き換えることができます.交換する場合は、必ずカップラーメンに最も少ない問題に交換してください.この部分はまずQでカップ麺が一番少ないものを選びましょう
上に暇があれば入れると書いてありますが、正確にはどんな条件ですか?これは、現在確認されている問題の分機数が、前に議論した問題数より大きいことを意味する.いつ解答するかは決まっていませんが、111日から連続解答と考えられます.これで全部左に押すと必ず残り時間がありますだからきっと入れられる

3.実施

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Pair> S = new ArrayList<>(N);
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int d = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			S.add(new Pair(d, v));
		}
		Collections.sort(S);
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (Pair x : S) {
			if (pq.size() < x.deadline) {
				pq.offer(x.value);
			} else if (pq.peek() < x.value) {
				pq.poll(); pq.offer(x.value);
			}
		}
		int sum = 0;
		for (int x : pq) sum += x;
		System.out.println(sum);
	}

}

class Pair implements Comparable<Pair> {
	int deadline, value;
	
	Pair(int d, int v) { deadline = d; value = v; }
	
	@Override
	public int compareTo(Pair o) { return deadline - o.deadline; }
	
}

1）時間複雑度

O(NlgN)O(NlgN)O(NlgN)