글 읽기 - 반례 부탁드립니다..

wogus23 3년 전 0

게시판의 반례 모두 대입 해 보았습니다.

그리고 플러그에서 뽑을 우선순위를

1. 사용하고 있는 전원 중 앞으로 사용하지 않을 전원을 제거

2. 1에서 선택 된 것이 없으면 가장 나중에 쓸 전원 선택 후 제거.

입니다. ㅠㅠ

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int plug, use,cnt=0;
	cin >> plug >> use;
	int*state = new int[use + 1]();// 사용 중인지 아닌지
	int*freq = new int[use + 1]();//빈도 수 
	deque<int>list(use);
	for (int i = 0; i < use; i++)
		cin >> list[i],freq[list[i]]++;
	
	while (!list.empty())
	{
		int cur = list.front();
		list.pop_front();

		if (state[cur])//사용될 장치가 이미 plug에 있으면 사용빈도 -1후 continue
		{
			freq[cur]--;
			continue;
		}
		if (plug > 0)
			state[cur] = true, plug--,freq[cur]--;
		else
		{
			//사용 중인 것 들 중 안 쓰 는 것 이 있 으 면 뽑음.
			bool det = false;
			for(int i=1;i<=use;i++)
				if (state[i] && freq[i]==0)//사용하고있고 앞으로 사용되지 않을 전원 
				{
					state[i] = false;
					state[cur] = true;
					freq[cur]--;
					det = true;
					cnt++;
					break;
				}

			if (det)
				continue;

			//없으면 가장 나중에 쓰는 놈을 선택 후 제거
			int Position = -1;
			int PlugNum = -1;
			for (int i = 1; i <= use; i++)
			{
				if (state[i])//사용 중 인것 선택
				{
					for (int j = 0; j < list.size(); j++)
					{
						if (i == list[j] && Position < j)//앞으로 사용될 목록중 가장 나중에 쓸 플러그 선택
						{
							Position = j;
							PlugNum = list[j];
						}
					}
				}
			}

			state[PlugNum] = false;
			state[cur] = true;
			cnt++;
		}

		
	}
	cout << cnt;
}

kth990303 3년 전 1

지나가다가 반례 있어서 달고 가요~

Input

3 14
1 4 3 2 5 4 3 2 5 3 4 2 3 4

Ans: 4

Wrong: 6

wogus23 3년 전 0

@kth990303 잊고 있었는데 다시 봐야겠네요 감사합니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다..

wogus23 3년 전 0

kth990303 3년 전 1

wogus23 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말