글 읽기 - 시간초과 줄이는법좀..

forybm 8년 전 0

이중포문을 어떤식으로 고쳐야 할까요??

#include <stdio.h>
#include <algorithm>

using namespace std;

int H[500000]={0};

int main()
{
	int length,high;  //동굴의 길이, 동굴의 높이 
	int n[200000]; //종유석 갯 
	
	scanf("%d%d",&length,&high);
	
	for(int i=1;i<=length;i++)
	{
		scanf("%d",&n[i]);
	}

	for(int i=1;i<=length;i++)  
	{
		if(i%2==0)  //짝수번째 종유석은 위세어 아래로 
		{
			for(int j=high;j>=1;j--)
			{
				H[j]++;
				n[i]--;
				if(n[i]==0) break;
			}
		
		}
		if(i%2==1) //홀수번째 종유석은 아래에서 위 
		{
			for(int j=1;j<=high;j++)
			{
				H[j]++;
				n[i]--;
				if(n[i]==0) break;
			}
		}
			
	}
	int count=0;
	sort(H+1,H+high+1);
	for(int i=1;i<=high;i++)
	{
		if(H[1]==H[i]) count++;
		else if(H[i]>H[1]) break;
	}
	printf("%d %d",H[1],count);
	
	
}

sang7 8년 전 0

종유석의 크기가 1이 3개 2가 3개 3 이 4개 일때 N = 10

1 이하의 방해물은 N - 0 개 = 10개

2 이하는 N - 3개 = 7개

3이하는 N- 6개 = 4개

다 샐 필요는 없다고는 생각이 듭니다.

한방향의 종유석을 정렬 후 이분 탐색으로 적절한 지점을 찾으신다면 시간 초과 없이 통과 가능합니다.

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

문제

문제

출처

ICPC

시간초과 줄이는법좀..

forybm 8년 전 0

sang7 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말