s7d8f9   2년 전

이 문제를 처음 보았을때 인덱스를 통한 정렬을 생각을 하였는데 시간초를 계산해볼때 10만개의 배열에서 

최악의 경우 계속 마지막 것만 물어보게 된다면 10만 *5000해서 5억정도의 시간이 걸릴 것 같아서 안되겠구나 하고

고민을 해보다 정 안되겠어서 다른 분들의 코드를 읽어보았는데 대부분 이 방식으로 푸신것 같습니다.


제 생각에서 어디가 잘못된 것이 있나요 ?... 아니면 테스트 케이스에서 마지막 것만 찾는 케이스가 없어서 그런건가요?.



#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 4000005
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

typedef struct st
{
    int num;
    int idx;
}str1;

bool cmp(str1 a, str1 b) {
    return a.num < b.num;
}

int n, k, i, j, cnt = 0, st, fi, target;
str1 map[5000005];

int main()
{
    
    scanf("%d %d", &n, &k);
    
    for (i = 0; i < n; i++)
    {
        scanf("%d", &map[i].num);
        map[i].idx = i+1;
    }
    
    sort(map, map+n, cmp);
    
    for (i = 0; i < k; i++)
    {
        scanf("%d %d %d", &st, &fi, &target);
        
        for (j = 0; j < n; j++)
        {
            if (st <= map[j].idx && map[j].idx <= fi)
                cnt++;
            
            if(cnt == target)
            {
                printf("%d\n", map[j].num);
                break;
            }
            
        }
        cnt = 0;
        
    }
}

jh05013   2년 전

카테고리를 질문으로 바꾸면 문제 번호와 소스코드를 넣는 칸이 있습니다.

s7d8f9   2년 전

죄송한데 그렇다면 5억의경우 코드를 간단하게 짜게된다면 1초안에 통과가 가능하다는 의미인가요?

djm03178   2년 전

초간단한 연산의 경우 10~20억 번도 가능합니다. https://www.acmicpc.net/proble... 이 문제의 경우 하나씩 연산하면 최대 10억 번 정도 반복문을 돌아야 하지만 약 600MS 정도에 통과되는 일이 있어 시간 제한이 1초에서 0.1초로 줄어들게 되었습니다.

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