전체 글 썸네일형 리스트형 BOJ)9426 중앙값 측정 문제: icpc.me/9426 n개의 수열이 있을 때 K의 연속 부분 수열의 중앙값의 합을 구하는 문제이다. 앞에서부터 K개의 수를 세그먼트 트리에 업데이트 시켜준 후 N까지 1개씩 지우고 업데이트 시켜주면서 중앙값을 구해주면 된다. 중앙값은 앞에서부터 (k+1)/2 수를 찾으면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include #define MAX_N 250001#define MAX 65536using namespace std;typedef long long ll;ll seg[4 * MAX_N], a[MAX_N], n, k, res;ll update(ll pos, ll val, ll node, ll x, .. 더보기 BOJ)5676 음주 코딩 문제: icpc.me/5676 값의 갱신이 일어날 때 i~j까지 모든 수를 곱했을 때 음수인지 양수인지 0인지 판단하는 프로그램을 작성하는 문제이다. 음수인지 양수인지 0인지만 판단하면 되므로 세그먼트 트리를 이용한 구간 곱으로 쉽게 구할 수 있다. 입력된 수가 양수일 경우 1 음수일 경우 -1 0일 경우 0으로 값을 갱신해주며 쿼리에 따른 값을 출력해 주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #define MAX_N 100000using namespace std;int seg[4 * MAX_N], n, k, a[MAX.. 더보기 BOJ)12016 라운드 로빈 스케줄러 문제: icpc.me/12016 0번 작업부터 N-1번 작업까지 순서대로 수행 할 때 스케줄러는 한 작업을 1초 실행 시킨 뒤 다음 작업으로 넘어간다고 한다. 이 때 각 작업들이 언제 완료 되는지 구하면 된다. 우리는 문제를 풀기위해 쿼리를 전부 받은 뒤 정렬하여 가장 짧은 작업부터 수행해보자. 한 작업을 끝냈을 때 다음작업은 이미 끝난 작업의 완료하는데 필요한 수행시간을 포함한다. 따라서 한 작업이 끝날 때 마다 이미 끝난 작업의 총 수행시간은 따로 더해서 저장할 필요가 있다. i번째 작업을 할 때 i번째 작업을 완료하는데 필요한 시간을 t라고 하면 답= (1~i번째 작업중 끝나지 않은 작업의 수)*t+(i+1~N번째 작업중 끝나지 않은 작업의 수)*(t-1) + (이미 끝난 작업의 총 수행시간) 이 .. 더보기 이전 1 ··· 103 104 105 106 107 108 109 ··· 118 다음