티스토리 뷰

 

bi = (ai*2-1,ai*2)일 때 1~2n 까지 숫자를 두는게 가능한지 보는 문제다

그리디로 내가 앞에서부터 작은수를 채워나가면 된다

 

이럴때는 upper_bound를 쓰자!!

 

먼저 set에 1~2n까지 나오지 않은 숫자를 담아준다

그리고 upper_bound를 통해 현재 위치를 만족시켜주는 가장 작은 숫자를 찾자

만약 없다면 -1!

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool check[222];
int main(){
    int t; scanf(" %d",&t);
    while(t--){
        memset(check,0,sizeof(check));
        int n; scanf(" %d",&n);
        vector<int> barr(n),ans(n);
 
        for(int i=0;i<n;i++){
            scanf(" %d",&barr[i]);
            check[barr[i]]=true;
        }
        set<int> s;
        for(int i=1;i<=n*2;i++){
            if(check[i]) continue;
            s.insert(i);
        }
 
        bool c=true;
        for(int i=0;i<n;i++){
            auto pos = s.upper_bound(barr[i]);
            if(pos==s.end()){
                c=falsebreak;
            }
            ans[i]=*pos;
            s.erase(*pos);
        }
        if(!c){
            puts("-1"); continue;
        }
        for(int i=0;i<n;i++printf("%d %d ",barr[i],ans[i]); puts("");
    }
}
 
 
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함