221006 문제 풀이 기록
2022. 10. 6. 23:20
P4 | 6142 - Gourmet Grazers
풀이 시간: 20분
시도 횟수: 1회
체감 난이도: P4 하위권
풀이 쓸 의향: 下
풀이
더보기
각각의 pair 배열을 green 내림차순 정렬 후, 마트 재고 중 해당 greenness보다 큰 grenness를 가진 것들 중 비용이 최소 비용 이상인 가장 작은 물품 구매하기. multiset lower_bound로 쉽게 해결 가능.
여담: 풀이가 빠르게 떠올라서 쉽게 풀었다.
P4 | 14449 - Balanced Photo
풀이 시간: 15분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
더보기
값 압축을 통해 h_i를 [1, N] 사이 범위로 바꿔준 뒤, 순서대로 [해당 값, N] 사이의 원소의 개수를 segtree로 세어주며 l_i, r_i 구하기
여담: 값 압축 안하고 키 내림차순 정렬 후 세그트리를 써도 풀린다. 세그트리에 순서를 넣는다는 아이디어보다 압축된 값을 넣는다는 아이디어가 더 빠르게 떠올라서 그냥 값 압축 세그트리를 쓰긴 했지만...
뭔가 두 문제 다 너무 빨리 풀어서 날먹한 기분... 뭐지?
'PS > 풀이 기록장' 카테고리의 다른 글
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
|---|---|
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |
| 221002 문제 풀이 기록 (0) | 2022.10.02 |