어려움: 2500
징후
설명
1. 좋아하는 사람에 따라 책을 나누자.
Alice가 가장 좋아하는 책을 1로, Bob이 가장 좋아하는 책을 2로 분류해 봅시다.
둘 다 좋으면 1+2=3으로 분류하고, 둘 다 싫다면 0으로 분류한다.
2. 범주 2 책보다 범주 1 책을 더 적게 읽는다면 어떻게 책을 읽을 수 있습니까?
\( C_i \) = \( i \) 최소한 몇 권의 책을 읽어야 하는지가 조건이라고 가정합니다.
그러면 질문 (2)는 \( C_1 \le C_2 \)라는 추가 조건을 암시합니다.
여기서 \( C_1 \)을 수정합니다.
Alice는 최소한 \( k \)개의 재미있는 책을 읽어야 하므로 최소한 \( \max(k – C_1, 0) \) 카테고리 3의 책을 읽어야 합니다.
카테고리 2의 책은 추가한 조건에 따라 \( C_1 \) 이상 읽어야 합니다.
범주 0의 책은 \( 0 \)개 이상의 책을 읽을 수 있으며 범주 1의 책은 \( C_1 \)이 설정되어 있으므로 더 이상 읽을 수 없습니다.
같은 카테고리의 책 중에서 확실히 읽는 데 시간이 덜 걸리는 책을 먼저 읽어야 합니다.
그러니 각 카테고리의 꼭 읽어야 할 책들을 시간이 가장 적게 걸리는 책들로 채우자.
그 후에는 원하는 대로 카테고리 0, 2, 3의 책을 더 읽을 수 있습니다.
그러나 한 가지 조건이 남아 있습니다. \( m \)개의 책을 정확히 읽어야 합니다.
우리는 지금까지 \( C_1 + C_1 + \max(k – C_1, 0) \) 책을 읽었습니다. 이를 바탕으로 남은 책의 수를 계산할 수 있습니다.
물론 이 남은 책들은 시간이 촉박한 분들도 사용하실 수 있습니다…
이제 분류와 관계없이 빠르게 읽을 수 있는 \(k\) 권의 시간 합계를 계산해야 합니다.
그래서 세그먼트 트리를 사용하려고 합니다.
\( i \)번째 리프 정점에서 책을 읽을 수 있는지 여부에 따라 다음 두 가지 경우 중 하나에 넣습니다.
// 읽을 수 없는 경우는 다음 두 경우 중 하나입니다.
// 1. 이미 읽은 책인 경우 / 2. 카테고리 1에 속하는 책으로 읽지 않아야 하는 경우
- 여전히 책을 읽을 수 있는 경우: (\( i \)번째로 빠른 책 시간, 1)
// \( i \)번째 리프 정점에 \( i \)번째로 가장 빠른 읽기 시간을 가진 책을 놓습니다!
// 우리가 읽은 여분의 책이 접두사에 수집되기 때문입니다. - 이 책을 읽을 수 없다면: (0, 0)
그래서 우리는 그 사이의 꼭지점에서 계산할 수 있습니다(간격의 모든 책을 읽는 데 걸리는 시간, 간격의 책 수).
이제 세그먼트 트리에서 이진 검색을 수행해 보겠습니다.
책의 수는 구간에 저장되어 있으므로 세그먼트 트리의 루트에서 \( x \)번째 책을 이진 검색할 수 있습니다.
또한 이 간격 안에 책을 읽는 데 걸린 시간을 저장하기 때문에 \( x \)개의 책을 읽는 데 걸린 시간을 계산하여 내려갈 수 있습니다.
0에서 1씩 증가시키면서 \( C_1 \)를 계산하면,
꼭 읽어야 할 책과 추가로 읽을 수 있는 책은 카테고리별로 최대 1권씩 변경된다.
흔들리는 느낌으로 처리 할 수 있습니다.
사실 위의 절차만으로도 전체 문제를 해결할 수 있습니다.
\( C_1 \ge C_2 \)의 경우 Alice와 Bob은 반대로 처리될 수 있습니다.
3. 역추적을 위해 추가로 구현해야 할 사항
먼저 계산 과정에서 답을 업데이트할 때마다 좋아하는 카테고리의 책을 적게 읽은 사람과 읽은 책의 수를 업데이트하면
이후 모든 계산이 완료된 후 상태(인원수, 권수)로 돌아가서 다시 과정에 따라 선택한 권의 권수를 하나씩 출력합니다.
4. 코드
|
하나
2
삼
4
5
6
7
8일
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
내부 n,m,k;
벡터<파이3> V(4);
끊임없는 내부 N = 262144;
파이2세그(524290);
비어 있는 업데이트하려면(내부 위치, pi2 값) {위치 += N–하나;
//cout << "UPD" << 위치-N+1< " -> ” << val.fr << ' ' << val.sc << endl;
부분 = 값; 위치 >>= 하나;
~하는 동안 (위치) {
세그(위치).fr = 섹션(위치<<하나).정말로 + 섹션(위치<<하나|하나).정말로;
세그(위치).sc = 섹션(위치<<하나).sc + 섹션(위치<<하나|하나). sc;
위치 >>= 하나;
}
}
내부 k번째(내부 케이){
내부 아니요 = 하나;
만약에 (케이 == 0){ 돌려 주다 0; }
내부 입술 = 0;
~하는 동안 (아니요 < N){
만약에 (케이 <= 세그먼트(아니요<<하나).sc){ni = 아니요<<하나; }
다른{케이 –= 세그먼트(아니요<<하나). sc; 입술 += 세그먼트(아니요<<하나).정말로; 아니요 = 아니요<<하나|하나; }
//cout << "KTH" << k << ' ' << res << ' ' << ni << endl;
}
돌려 주다 입술 + seg(ni).fr;
}
끊임없는 내부 INF = 2147483647;
내부 에게 = INF; 파이2 조정 = {0, 0};
비어 있는 해결하다(내부 인자){
~을 위한 (내부 나 = 하나; 나 < N+N; 나++){ 섹션(i) = {0, 0}; }
~을 위한 (pi3p: v(0)){ upd(p.fr.sc, {p.fr.fr, 하나}); }
~을 위한 (pi3p: v(2)){ upd(p.fr.sc, {p.fr.fr, 하나}); }
~을 위한 (pi3p: v(삼)){ upd(p.fr.sc, {p.fr.fr, 하나}); }
내부 l0 = V(0).크기(), l1 = V(하나).크기(), l2 = V(2).크기(), l3 = V(삼).크기();
내부 입술 = 0;
내부 c3 = 최소(k, l3);
~을 위한 (내부 나 = 0; 나 < c3; 나++){
pi2p = V(삼)(i).fr;
업데이트(p.sc, {0, 0}); 입술 += S.fr;
}
~을 위한 (내부 c1 = 0; c1 <= 중; c1++){
만약에 (c1 > 0){
만약에 (c1 > l1 || c1 > l2){ 부서지다; }
파이2피1 = V(하나)(c1–하나).fr, p2 = V(2)(c1–하나).정말로;
업데이트(p1.sc, {0, 0}); 입술 += p1.fr;
업데이트(p2.sc, {0, 0}); 입술 += p.2. fr;
}
만약에 (c3 > 최대 (n–c1, 0)){
파이2 피3 = V(삼)(c3–하나).정말로;
업데이트(p3.sc, {p3.fr, 하나}); 입술 –= 3면. fr; c3 –= 하나;
}
만약에 (c3 < 최대 (n–c1, 0)){ 계속해; }
내부 cnt = c1+c1+c3;
만약에 (현재 > 중){ 부서지다; } 만약에 (N–(l1–c1) < 중){ 계속해; }
내부 값 = 입술 + k번째(m–cnt);
//cout << 인수 << ' ' << c1 << ' ' << c3 << ' ' << cnt< " -> ” << 응답 << ' ' << 값 << endl;
만약에 (값 < 답변) {답 = 값; 조정하다 = {인수,c1}; }
}
}
비어 있는 주로(){
친 >> N >> 중 >> 케이;
벡터<파이2> srt;
~을 위한 (내부 나 = 하나; 나 <= N; 나++){
내부 x,a,b; 친 >> 엑스 >> ㅏ >> 비;
내부 아이디엑스 = 2*ㅏ + 비;
v(idx).푸시백({{엑스, 0}, 나});
srt.푸시백({x,idx});
}
~을 위한 (내부 나 = 0; 나 < 4; 나++){ 정렬(모두(v(i))); } 정렬(모두(srt));
벡터<파이3>::반복자 그것(4); ~을 위한 (내부 나 = 0; 나 < 4; 나++){ 나) = v(i).시작하다(); }
내부 나 = 0; ~을 위한 (pi2 p:srt){i += 하나;
(*es(p.sc)).fr.sc = 나; 그것은 (p.sc)++;
}
해결하다(0); 스왑(v(하나), V(2)); 해결하다(하나);
만약에 (답 == INF){ 쿠우트 << –하나; 돌려 주다; } 다른{ 쿠우트 << 에게 << 끝; }
만약에 (adapt.fr == 0){ 교환 (v(하나), V(2)); }
내부 cnt = 조정하다 sc;
내부 c0 = 0c1 = cnt, c2 = cnt, c3 = 최대 (n–씨엔티, 0);
~을 위한 (내부 나 = 0; 나 < c1; 나++){ 쿠우트 << V(하나)(i).sc << ”; }
~을 위한 (내부 나 = 0; 나 < c2; 나++){ 쿠우트 << V(2)(i).sc << ”; }
~을 위한 (내부 나 = 0; 나 < c3; 나++){ 쿠우트 << V(삼)(i).sc << ”; }
벡터<파이2> 값;
~을 위한 (내부 나 = c0; 나 < V(0).크기(); 나++){ 값.푸시백({V(0)(i).fr.fr, v(0)(i).sc}); }
~을 위한 (내부 나 = c1; 나 < V(하나).크기(); 나++){ 값.푸시백({V(하나)(i).fr.fr, v(하나)(i).sc}); }
~을 위한 (내부 나 = c2; 나 < V(2).크기(); 나++){ 값.푸시백({V(2)(i).fr.fr, v(2)(i).sc}); }
~을 위한 (내부 나 = c3; 나 < V(삼).크기(); 나++){ 값.푸시백({V(삼)(i).fr.fr, v(삼)(i).sc}); }
정렬(모두(값));
내부 왼쪽 = 중 – (c1+c2+c3);
~을 위한 (내부 나 = 0; 나 < 왼쪽; 나++){ 쿠우트 << 발(i).sc << ”; }
}
|
CS |