[백준]22345 - 누적거리 (누적합)

https://www.acmicpc.net/problem/22345

22345번: 누적 거리

수직선 위에 n개의 마을이 존재하고

각 마을엔 nn명이 거주하고있다

파티를 개최할 장소 q개에 대해

모든 사람들이 해당 장소로 이동하는데 필요한 각각의 누적 거리를  구하라

 

그냥 문제에 주어진대로

주어진 위치와 각 마을과의 거리를 구하고 인구수를 곱한 총합을 구하면

시간 초과가 발생한다

 

그렇기에 누적 합이란 개념을 사용해야 하는데

1번째 총합은 기존과 똑같이 구하고,

2분째 총합부터는 이전에 구한 값을 이용하여 답을 구해야한다

 

Q 지점에 대해 각 거리의 합은 위와 같고

 

절대값을 제거하면 이렇게 된다

Q보다 큰 첫 지점은 lower_bound() 내장함수를 사용한다

 

식을 정리해주고

 

해당 식을 코드로 구현해주면 끝

 

 

 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
const int MAX = 200011;
ll N, Q, d[MAX], k[MAX];
typedef pair<ll, ll> llll;
vector <llll> a;
vector <ll> v;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		ll aa, xx;
		cin >> aa >> xx;
		a.push_back({ xx,aa });
		v.push_back(xx);
	}
	sort(all(a));
    sort(all(v));
	for (int i = 1; i <= N; i++) { 
		d[i] = d[i - 1] + a[i - 1].first * a[i - 1].second;
		k[i] = k[i - 1] + a[i - 1].second;
	}
	while (Q--) {
		ll n;
		cin >> n;
		ll idx = lower_bound(all(v), n) - v.begin();
		cout << d[N] - 2 * d[idx] - (n * (k[N] - 2 * k[idx])) << "\n";
	}
}