문제 링크
https://www.acmicpc.net/problem/23829
문제
태영이는 SASA의 축제라고 불리는 "인문예술탐사주간"을 보내게 되었다. "인문예술탐사주간"을 맞이하여 세종호수공원에 가게 된 태영이는 아름다운 경치에 놀라움을 금치 못했다.
세종호수공원은 일직선으로 뻗어있는 모습이다. 이 공원에는 나무가 총 N그루 있으며, i번째 나무의 위치는 Pi이다.
태영이는 카메라를 들고 파노라마 사진을 Q번 찍어, 이 아름다운 풍경을 담으려고 한다. 태영이는 이 사진에 점수를 매기려고 하는데, 사진의 점수는 사진을 찍은 위치로부터 각 나무까지의 거리 합이다. 이 때, 두 위치의 거리는 두 위치의 차의 절댓값으로 정의된다.
태영이가 찍은 사진에 대해서, 각 사진의 점수를 매겨주자.
입력
첫째 줄에는 나무의 개수 N과 태영이가 찍은 사진의 개수 Q가 공백으로 구분되어 주어진다.
둘째 줄에는 나무의 위치 P1,P2,⋯,PN이 주어진다.
셋째 줄부터 Q개의 줄의 i번째 줄에는 태영이가 i번째로 사진을 찍은 위치 Xi가 주어진다.
출력
i번째 줄에는 태영이가 i번째 찍은 사진의 점수를 한 줄에 하나씩 차례대로 출력한다.
제한
- 1≤N,Q≤10^5
- 1≤Pi≤10^7(1≤i≤N)
- 1≤Xi≤10^7(1≤i≤Q)
- 입력으로 주어지는 모든 수는 정수이다.
예제 입력 1
5 2
1 3 7 9 10
4
12
예제 출력 1
18
30
알고리즘 분류
- 이분 탐색
- 누적 합
풀이
lower_bound를 생각 못 하고 풀었다가 시간 초과 발생..
사진을 찍은 위치 X보다 왼쪽에 위치한 나무들의 위치 합을 (X * 왼쪽에 위치한 나무들의 개수)에서 빼주면, X보다 왼쪽에 위치한 나무들 간의 거리의 차의 합이 구해진다.
마찬가지로 오른쪽에 위치한 나무들의 위치 합에서 (X * 오른쪽에 위치한 나무들의 개수)를 빼주면 X보다 오른쪽에 위치한 나무들 간의 거리의 차의 합이 구해진다.
구한 값 2개를 합하면 원하는 값이 나온다.
코드
#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9
using namespace std;
int N, Q;
vector<int> P;
LL Sum[MAX];
void Input() {
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
int X;
cin >> X;
P.push_back(X);
}
}
void Settings() {
sort(P.begin(), P.end());
for (int i = 1; i <= N; i++) {
Sum[i] = Sum[i - 1] + P[i - 1];
}
}
void Find_Answer() {
while (Q--) {
LL X;
cin >> X;
int Cnt = lower_bound(P.begin(), P.end(), X) - P.begin();
LL Small = Sum[Cnt];
LL SP = (X * Cnt) - Small;
LL Big = Sum[N] - Small;
LL BP = Big - (X * (N - Cnt));
cout << BP + SP << "\n";
};
}
int main() {
FASTIO
Input();
Settings();
Find_Answer();
return 0;
}
'BOJ > Gold' 카테고리의 다른 글
[BOJ/Gold 3] 백준 2900 프로그램(C++) (0) | 2022.04.06 |
---|---|
[BOJ/Gold 4] 백준 14846 직사각형과 쿼리(C++) (0) | 2022.04.05 |
[BOJ/Gold 4] 백준 17305 사탕 배달(C++) (0) | 2022.04.03 |
[BOJ/Gold 4] 백준 5549 행성 탐사(C++) (0) | 2022.04.03 |
[BOJ/Gold 4] 백준 2313 보석 구매하기(C++) (0) | 2022.04.02 |