안주녕

농부 존은 소유하고 있는 소들의 사진을 찍기 위해 전문 사진 작가를 고용했다. 다양한 품종의 소를 소유하고 있는 존은 한 장의 사진에 모든 종의 소가 포함 되길 원한다. N 마리의 소가 모두 라인에 맞춰(즉, Y 좌표는 고정) 다양한 위치(즉, X 좌표로 값은 정수 값임)에 서 있다. 그리고 소들은 정수 값의 품종 아이디를 목에 걸고 있다. 존은 연속된 범위의 사진을 찍을 계획이다. 사진 비용은 크기에 비례한다. 즉, X 좌표의 범위가 작을수록 비용은 저렴해진다. 당신이 할 일은 존이 한 장의 사진에 모든 품종의 소들이 적어도 한 마리씩은 포함될 수 있게 하는 최소 비용을 계산하는 것이다. 입력 첫 번째 줄에 소들의 수 N이 입력된다. (1≤N≤50,000) 두 번째 줄부터 N개 줄에 걸쳐 소의 위치 (X 좌표)와 소의 품종 아이디(ID)가 공백으로 구분되어 입력된다. (1≤X, ID≤1,000,000,000) 출력 모든 품종이 포함되는 X 좌표의 최소 범위를 출력하라. 입력 예시 6 25 7 26 1 15 1 22 3 20 1 30 1 #include <cstdio> #include <map> #include <algorithm> #define MAXN 50000 using namespace std; map<int,int> C; pair<int,int> cows[MAXN]; int N,K; int photo(){ int i,j,k; int min_cost = cows[N-1].first-cows[0].first; i = 0, j = -1, k = 0; while(i < N && j < N){ while(k < K && ++j < N) k += !(C[cows[j].second]++); while(k >= K){ min_cost = min(min_cost,...

회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.       새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.   1.  원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.  2.  각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.   위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.   회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최대값을 구하는 프로그램을 작성하시오. 입력 입력의 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번...