글 읽기 - c++ priority_queue로 푼것 반례가 있을까요?

mun9769 2년 전 0

priority_queue는 1.우선순위가 클수록, 2. 실행시간이 작을수록, 3. 아이디가 작을 수록, 을 만족하여 push할 수 있습니다.

"기다리는 프로세스의 우선순위를 단위시간당 1씩 증가한다 = 최근에 들어온 프로세스의 우선순위를 생성된 시간에 비례해서 감소한다."

라는 생각으로 문제를 접근했습니다.

saveTime은 실행요청된 시간이 같은 프로세스들을 한번에 받아주기 위한 변수입니다.

sum은 진행중인 프로세스가 끝나는 시점을 의미합니다.

반례가 궁금합니다.

#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <queue>
using namespace std;

class proc
{
public:
    proc() {}
    proc(int id, int t, short p, short b) : id(id), t(t), p(p), b(b) {}
	int id = 0;
    int t = 0;
    short p = 0;
	short b = 0;
};
vector<int> result;

struct cmp {
	bool operator()(proc& a, proc& b)
	{
		if (a.p == b.p)
		{
			if (a.b == b.b)
			{
				return a.id > b.id;
			}
			return a.b > b.b;
		}

		return a.p < b.p;
	}
};

int n;
short t, p, b;
std::priority_queue<proc, vector<proc>, cmp> pq;

int sum = 0;

int main()
{
    cin >> n;

	int runTime = 0;
	int saveTime = -1;

	proc* procs = new proc[300'001];

	for(int i=1; i<=n; i++)
	{
		cin >> t >> p >> b;
		procs[i] = proc(i, t, p, b);
	}

	int i = 1;
	
	for (i = 1; i <= n;)
	{
		saveTime = procs[i].t;

		while (!pq.empty() && sum < procs[i].t)
		{
			proc p = pq.top();
			pq.pop();
			sum += p.b;
			result.push_back(p.id);
		}

		while (saveTime == procs[i].t && i <= n)
		{
			proc process(i, procs[i].t, procs[i].p - procs[i].t, procs[i].b);
			pq.push(process);
			i++;
		}
	}

	while (!pq.empty())
	{
		proc p = pq.top();
		pq.pop();
		result.push_back(p.id);
	}

	for (auto ele : result)
	{
		cout << ele << " ";
	}
	delete[] procs;
    return 0;
}

dlwjsgud12 4달 전 0

안녕하세요 제가 새로 작성한 글이 도움이 될 수 있을 것 같습니다

https://www.acmicpc.net/ㅇboard/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ priority_queue로 푼것 반례가 있을까요?

mun9769 2년 전 0

dlwjsgud12 4달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말