백준 12892번 생일 선물 C++

출처 : https://www.acmicpc.net/problem/12892

 

가격을 기준으로 내림차순으로 정렬한 뒤 투 포인터를 이용해 가격의 차이가 D 이상이면 왼쪽 포인터를 늘리고 아니라면 오른쪽 포인터를 늘리는 방식으로 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

bool compare(const pair<int, int>& lhs, const pair<int, int>& rhs) {
	return lhs.first > rhs.first;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, d;
	cin >> n >> d;
	vector<pair<int, int>> presents(n);
	for (int i = 0; i < n; i++) {
		int p, v;
		cin >> p >> v;
		presents[i] = { p,v };
	}
	sort(presents.begin(), presents.end(), compare);
	int left = 0;
	int right = 0;
	ll sum = 0;
	ll ans = 0;
	while (right < n) {
		if (presents[left].first - presents[right].first >= d) {
			sum -= presents[left].second;
			left++;
		}
		else {
			sum += presents[right].second;
			right++;
		}
		ans = max(ans, sum);
	}
	cout << ans;
};