글 읽기 - 문제를 풀긴 풀었는데 시간복잡도가 궁금합니다.

cgc96 4년 전 0

아래와같이 코드를짜면 시간복잡도를 어떻게 계산하나요?

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

int n;
vector<pair<int, int>> v;

bool cmp(const pair<int, int> a, const pair<int, int> b){
    if(a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int main(){
    int n; scanf("%d", &n);

    for(int i = 0; i < n; i++){
        int x, y; scanf("%d %d", &x, &y);
        if(x < y) v.push_back({x, y});
        else v.push_back({y,x});
    }
    int d; scanf("%d", &d);

    sort(v.begin(), v.end(), cmp);

    int Max = 0;
    multiset<int> s;
    
    for(int i = 0; i < n; i++){
    	if(v[i].second-d <= v[i].first){
    		s.insert(v[i].first);
    	}
    	set<int>::iterator iter;
    	for(iter = s.begin(); iter != s.end(); iter = s.begin()){
    		if((int)*iter >= v[i].second-d)
    			break;
    		s.erase(s.begin());
    	}
    	
    	Max = max(Max, (int)s.size());
    }
    
    printf("%d", Max);
    return 0;
}

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

문제

문제

출처

ICPC

문제를 풀긴 풀었는데 시간복잡도가 궁금합니다.

cgc96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말