백준 27896 특별한 서빙 C++

간단한 해설

처음에는 투포인터를 사용해서 문제를 풀려고했었다. 그러나

 

음식을 앞에 서있는 학생부터 순서대로 서빙할 때, 어떤 한 순간이라도 불만도가 M 이상이 되면 학생들은 ‘가지 운동’을 일으키게 된다.

 

이 지문때문에, 우선순위 큐로 관리해서 푸는 것이 해법임을 깨달았다.

 

처음부터 일단 음식을 파로 받는다. 그러다가 불만도가 M 이상이 되면, 제일 큰 값을 가지로 바꾸면 된다. (이때, 더해준 값을 빼준 값으로 바꿔야하므로 -2*x_i로 한다.)

 

답

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n,m;
	cin>>n>>m;
	vector<ll> v(n);
	for(int i=0;i<n;++i){
		cin>>v[i];
	} 
	priority_queue<ll> q;
	ll sum=0,ans=0;
	for(int i=0;i<n;++i){
		sum+=v[i];
		q.push(v[i]);
		while(sum>=m){
			ll val=q.top();
			sum-=2*val;
			q.pop();
			++ans;
		}
	}
	cout<<ans;
}