어민

한 작은 나라에서는 대부분의 시민들이 어부이며, 그 나라의 모든 마을은 직선 해변을 따라 건설된 직선 도로에 위치해 있다.
마을의 어부들은 엄청난 양의 물고기를 잡았으나 예전처럼 물고기를 좋아하지 않아서 이웃 나라의 가난하고 배고픈 아이들을 입양하기로 결정했다.
하나의 긴 직선 도로가 해변을 따라 모든 마을을 연결한다. 따라서 각 도시(첫 번째와 마지막 도시는 제외)는 두 이웃 마을에 직접 연결된다. 1년에 한 명의 어린이가 1톤의 물고기를 먹는다. 어떤 마을에서 잡힌 물고기의 양은 그 마을에서 먹거나 다른 마을로 옮길 수 있다.
도로를 이용해서 옮겨야 하는데 이용에 따른 세금이 부과된다. 1km당 1톤의 물고기를 세금으로 내야 한다.
각 마을마다 동등한 수의 가난한 아이들이 입양되기를 원한다. 각 마을에 수용될 수 있는 아이들의 최대 수를 결정하는 프로그램을 작성하시오. 모든 물고기가 잡히고 저렴하게 운반된 물고기를 먹을 수 있다는 조건이다.


입력

첫 번째 줄에는 마을 수 N(1≤N≤100,000, 정수)이 입력된다
두 번째 줄부터 N줄에 걸쳐 마을 정보가 입력된다. 마을 정보는 두 개의 정수A, B이며 공백으로 구분되어 입력된다. A는 도시의 위치이며 B는 잡힌 물고기 양이다. (1≤A≤1,000,000,000, 단위는 km) (0≤B≤1,000,000,000, 단위는 톤)
마을 정보는 도로 위치에 따라 오름차순으로 정렬되어 입력된다.

출력

각 마을에 동일한 수로 입양될 수 있는 최대 아이들 수를 출력하라

입력 예시

3
1 0
2 21
4 0

출력 예시

6

도움말

2번 마을에서 6톤+1톤(세금) = 7톤을 1번 마을로 보내고, 4번 마을에 6톤+2톤(세금) = 8톤을 보낼 수 있다. 남은 6톤을 2번 마을 아이들을 먹일 수 있으므로 최대 수는 6명이다.
입력 예2
3
5 70
15 100
1200 20
 
출력 예2
20
 
입력 예3
4
20 300
40 400
340 700
360 600
 
출력 예3
415



#include <stdio.h>
#define MAX 1000000
int N;
int midx = 0;
int min = 0;
long long A[MAX], B[MAX];

int absub(int a, int b){
if (a > b) return a - b;
else return b - a;
}

int check(int n) {
long long sum = 0;
long long t;
register int i;
for (i = 0; i < N-1; i++) {
t = B[i] - n;
sum += t;
if (sum >= 0 && (sum - (A[i + 1] - A[i])) <0) sum = 0;
else sum -= A[i + 1] - A[i];
}
sum += (B[N - 1]- n);
if (sum>=0) return 1;
else return 0;
}



int solve() {
register int i;
long long s = 0, e = B[midx], m;
long long sol = 0;

while (s <= e) {
m = (s + e) / 2;
if (check(m) == 1) {
sol = m;
s = m + 1;
}
else e = m -1;
}
if (sol == 0) return B[min];
return sol;
}

int main(void)

{

// 여기서부터 작성
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d %d", &A[i], &B[i]);
if (B[i] > B[midx]) midx = i;
if (B[i] < B[min]) min = i;
}

printf("%d\n", solve());
return 0;

}

댓글

댓글 쓰기

이 블로그의 인기 게시물

최소비용 포장

사탕 공장에서는 요구에 따라 다양한 개수의 사탕을 담고 있는 포장을 하고 있다. 어느 날 갑자기 대형 이벤트가 생겨서 공장에 있는 모든 사탕들을 풀어서 하나로 포장 해야 한다.   A, B, C 3 개의 사탕 포장이 있을 때 이 포장들을 한번에 하나로 합칠 수는 없고, 한번에 2개씩만 합칠 수 있다. 예를 들면 A와 B를 먼저 합친 후 C를 다시 합치거나 A와 C를 먼저 합치고 B를 합치기, 혹은 B와 C를 먼저 합치고 A를 합칠 수 있다.   사탕 포장을 풀었다가 다시 합치는 순서는 매우 중요한데, 그 이유는 그 순서에 따라 전체 비용이 달라지기 때문이다.   사탕 포장 A와 B에 각각 a개와 b개의 사탕이 들어있다고 할 때 이 둘을 합치는 비용은 a + b라고 한다. 그러므로 A와 B를 먼저 합치고 C를 합치는 경우 그 전체 비용은 a + b + a + b + c이며, B와 C를 먼저 합치고 A를 합치는 비용은 b + c + b + c + a 이므로 그 둘은 서로 같지 않을 수 있다.   예를 들어, 각각 2, 2, 5개가 포장되어 있다면 A(2)와 B(2)를 합치는 비용은 4. 합쳐진 것(4)과 C(5)를 합치는 비용은 9로 총 13이 최소비용이다.   현재 공장에 포장되어 있는 포장 개수 N과 각각 포장에 들어있는 사탕의 개수 ni가 주어질 때, 이들을 하나로 합치는데 들어가는 비용의 최소(C)를 구하라. 입력 첫 번째 줄에는 포장 개수 N(1<=N<=5000)이 주어진다. 두 번째 줄에는 포장에 들어있는 사탕의 개수 ni(1<=ni<=100)가 주어진다. 출력 최소 비용을 출력한다. 입력 예시 3 2 2 5 출력 예시 13 #include <stdio.h> #define MAX 5003 int N; int ni[MAX]; int tree[MAX]...
자세한 내용 보기

구슬집어넣기

철수의 동생이 다니는 학교에서는 ‘구슬 집어넣기 게임’ 선풍적인 인기를 끌고 있다. 철수 동생은 반 친구들과 이 게임의 성적을 놓고 경쟁을 하고 있다.    어느 날, 철수의 동생이 시무룩한 얼굴을 하고 집에 들어왔다. 친구들보다 좋은 성적을 내지 못했다고 우울했던 것이다. 그래서 철수는 동생을 위해 게임에서 최고 성적을 내는 방법을 알려주는 프로그램을 만들기로 했다.   게임은 다음 룰에 의해 진행된다.   1. 게임판에는 빨간구슬, 파란구슬, 벽, 그리고 목표구멍이 있다. 2.  플레이어는 총 10회 게임판을 기울일 수 있다. (방향 : 상하좌우) 3.  플레이어가 게임판을 기울이게 되면 해당 방향으로 빨간구슬과 파란구슬이 한 칸 이동한다. 4.  이동방향에 벽이 있는 구슬은 움직일 수 없다. 5.  이동 시 빨간 구슬과 파란 구슬이 같은 위치로 움직여 부딪히는 경우 구슬이 깨지므로, 게임 실패다. 6.  파란구슬이 목표구멍으로 들어가는 것은 게임 실패다. 7.  기울임 횟수가 10회를 넘어서면 게임 실패다. 8.  빨간 구슬이 목표구멍으로 들어가는 것이 이 게임의 목표이다. 9.  적은 횟수를 기울여 해결할수록 많은 높은 점수를 얻을 수 있다.   기본적으로 게임판의 가장자리는 구슬이 게임판 밖으로 빠져나가지 못하도록 벽으로 둘러쌓여 있다.   철수는 우선 이 게임에서 문제를 해결할 수 있는 가장 적은 횟수를 알고 싶다. 이를 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다. 이후부터 T개의 테스트 케이스 셋트가 주어진다. 셋트의 첫 번째 줄에는 게임판의 행(R)과 열(C)이 순서대로 주어진다. (3<=R,C<=15) 셋트의 두 번째 줄부터 게임판의 행만큼 게임판의 상황이 주어진다. (...
자세한 내용 보기