글 읽기 - 풀이 방법에 오류가 있을까요

p_ce1052 2년 전 0

선수들을 L값으로 먼저 정렬, L값이 같으면 P값의 오름차순으로 정렬.

팀 크기 정렬하고

작은 팀부터 만들어나갔습니다.

현재 만들 팀의 크기를 t라고 하면 선수들의 배열에서 맨 앞의 t-1명은 절대 (앞으로도) 리더가 될 수 없으므로 제거합니다.

남은 배열에서 최대 P값을 찾아 답에 더해주고 배열에서 제거합니다. 최대 p값이 여러개면 앞에있는걸 제거하는게 유리하므로 앞에있는거부터 제거

남은 팀들도 똑같이 반복.

구현상의 문제일까요? 제출하자마자 틀립니다 ㅠㅠ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
pi arr[300005];
ll team[300005];
bool v[300005];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n,m; cin>>n>>m;
	for(int i=1; i<=n; i++) cin>>arr[i].first>>arr[i].second;
	sort(arr+1,arr+n+1);
	for(int i=1; i<=m; i++) cin>>team[i];
	sort(team+1,team+m+1);
	ll ans = 0;
	priority_queue<pi,vector<pi>,less<pi>>pq;
	for(int i=1; i<=n; i++) pq.push(pi(arr[i].second,-i));
	int p = 1;
	for(int i=1; i<=m; i++){
		int t = team[i];
		for(int j=1; j<=t-1; j++){
			while(v[p]) p++;
			v[p] = 1;
		}
		while(pq.size() && v[-pq.top().second]) pq.pop();
		ans+=pq.top().first; v[-pq.top().second] = 1;
		pq.pop();
	}
	cout<<ans;
}

solarmagic 2년 전 1

3 2

3 100

2 1

1 99

1 2

이랬을 때 199가 정답 아닐까요

p_ce1052 2년 전 0

감사합니다 더 생각해 봐야겠네요

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

문제

문제

출처

ICPC

풀이 방법에 오류가 있을까요

p_ce1052 2년 전 0

solarmagic 2년 전 1

p_ce1052 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말