2095번 - 티켓 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 169 | 25 | 14 | 15.217% |
문제
N(1 ≤ N ≤ 30,000)개의 좌석으로 되어 있는 기차가 있다. 편의상 좌석에 1번부터 N번까지의 번호가 붙어있다고 하자. 철도 회사에서는 명절을 맞이하여 귀성하는 가족들에게 기차 티켓을 팔기로 하였다. 문제를 단순화하기 위해서, 편의상 모든 가족들은 L(1 ≤ L ≤ 100)명으로 이루어져 있다고 가정하자.
각 가족들은 다들 자신이 원하는 좌석이 있다. 즉, 각 가족들은 기차의 특정 좌석부터 연달아 L개의 좌석 티켓을 구매하려 한다. 이와 같이 구매하더라도 기차 티켓의 가격에는 차이가 없지만, 서비스에 만족한 고객들이 추후에 다시 기차를 이용할 가능성이 있기 때문에, 잠재적인 이익이 2만큼 발생하는 것으로 간주한다. 만약 가족에게 기차 티켓을 팔지 못하면 잠재적인 이익이 발생하지 않으며, 기차 티켓을 팔되 원하는 자리가 아닌 경우에는 잠재적 이익이 1이 된다.
각 가족들이 원하는 좌석이 주어졌을 때, 최대의 잠재적 이익을 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 N, L, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 정수 z(1 ≤ z ≤ N-L+1)가 주어진다. 이는 그 가족이 z번 좌석부터 z+L-1번 좌석까지를 구매하기를 원한다는 의미이다.
출력
첫째 줄에 최대 잠재적 이익을 출력한다.
예제 입력 1
20 3 7 4 2 10 9 16 15 17
예제 출력 1
9
힌트
1, 3, 5번 가족들에게 원하는 대로 판매하고, 4번 가족에게 1~3번을, 2번 가족에게 7~9번을, 6번 가족에게 13~15번을 판매하면 된다.
출처
Olympiad > Central European Olympiad in Informatics > CEOI 2005 > Day 2 6번
- 문제의 오타를 찾은 사람: tjdwo5313
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호