글 읽기 - 시간초가 원인을 모르겠습니다.

limsd2002 7년 전 0

시간초가 원인 자세히 설명 바랍니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int Ci[300001];
int visit[300001];

struct P{
	int Mi;
	int Vi;
} P;

struct P MV[300001];

bool cmp1(const struct P &i, const struct P &j){
	if(i.Vi==j.Vi) return i.Mi < j.Mi;
	else return i.Vi > j.Vi;
}

int main(){
	int T, test_case, N, K, sum;
	
	scanf("%d", &T);
	for(test_case=1; test_case<=T; test_case++){

		scanf("%d %d",&N,&K);

		for(int i=0; i<N; i++) {
			scanf("%d %d",&MV[i].Mi,&MV[i].Vi);
			visit[i]=0;
		}
		for(int i=0; i<K; i++) scanf("%d",&Ci[i]);
		
		sort(MV,MV+N,cmp1);
		sort(Ci,Ci+K);

		sum=0;
		int cnt=0;
		for(int i=0; i<K; i++)
			for(int j=cnt; j<N; j++)
				if(visit[j]==0 && MV[j].Mi <= Ci[i]) {
					sum += MV[j].Vi;
					visit[j] = 1;
					cnt = j;
					break;
				}
		printf("#%d %d",test_case, sum);
	}
	return 0;
}

sksdong1 7년 전 0

O(NK)

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

문제

문제

출처

ICPC

시간초가 원인을 모르겠습니다.

limsd2002 7년 전 0

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말