글 읽기 - 시간초과인데 정렬법이 잘못된건가요?

kkw564 8년 전 0

for(i = 0; i <= n-k ; i++)

{

if(ans[0] <= ans[i])

{

tmp = ans[0]; // temp는 임시저장소

ans[0] = ans[i];

ans[i] = tmp;

}

이 정렬법이 잘못된건가요??

시간초과라뜨네요

​#include<stdio.h>
int a[100005];

int ans[100005];

int main()

{

int n,k;

int i,j; // 반복문 변수

int tmp;

scanf("%d %d",&n,&k);

// while(getchar()!='\n'); // fflush(stdin);

for(i = 0 ; i < n ; i++)

{

scanf("%d",a+i);

}

for(i = 0; i <= n-k; i++)

{

ans[i] = a[i];

for(j = i+1 ; j <= i+(k-1) ; j++)

{

ans[i] = a[j]+ans[i];

// printf("i : %d j : %d ans[i] : %d\n",i,j,ans[i]);

}

}

for(i = 0; i <= n-k ; i++)

{

if(ans[0] <= ans[i])

{

tmp = ans[0]; // temp는 임시저장소

ans[0] = ans[i];

ans[i] = tmp;

}

}

printf("%d",ans[0]);

// sleep(1000000);

}

portal3046 8년 전 0

이중 포문에서 n이 십만, k가 5만 정도라면 25억번 돌게되는데 그러면 시간초과가 뜨겠네요

for(i = 0; i <= n-k; i++)

{

ans[i] = a[i];

for(j = i+1 ; j <= i+(k-1) ; j++)

{

ans[i] = a[j]+ans[i];

// printf("i : %d j : %d ans[i] : %d\n",i,j,ans[i]);

}

}

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

문제

문제

출처

ICPC

시간초과인데 정렬법이 잘못된건가요?

kkw564 8년 전 0

portal3046 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말