[Codeforces][Round #731][Div.3] C : Pair Programming (C++)

 

https://codeforces.com/contest/1547/problem/C

[난이도] Div.3
[유형] Greedy

[풀이]
Greedy 문제입니다.

a,b 배열의 index를 aidx, bidx로 유지하면서 a[aidx],b[bidx]중 하나를 선택해
ans vector에 추가해주는 식으로 풉니다. 정답이 존재한다면 ans vector의 크기가 n+m이 되어야 합니다.

a[adix],b[bidx] 중에 고르는 기준은 다음과 같습니다..
1) 둘중 0이 있는 경우 무조건 선택한다. 새로운 라인을 추가하는 것은 어떤 경우에도 유리하기 때문
2) 0이 없을때는 k (현재 페이지의 총 라인수) 보다 작거나 같은 값이 있으면 선택한다. 라인을 수정하는 것은
아직 선택되지 않은 것들에 어떤 악영향도 미치지 않으므로

aidx==n , bidx==m이 될때까지 위 과정을 반복하면 ans vector에 최종 정답이 저장됩니다.

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int tc;
int k,n,m,a[301],b[301];
 
void prt(){
    puts("a");
    for(int i=0;i<n;i++) printf("%d ",a[i]);
 
    puts("b");
    for(int i=0;i<m;i++) printf("%d ",b[i]);
}
 
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&k,&n,&m);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<m;i++) scanf("%d",&b[i]);
        vector<int> ans;
 
        int aidx=0,bidx=0;
        int it=m+n;
        while(it--){
            if(aidx<n){
                if(a[aidx]==0) {
                    k++;
                    aidx++;
                    ans.push_back(0);
                    continue;
                }
            }
            if(bidx<m){
                if(b[bidx]==0) {
                    k++;
                    bidx++;
                    ans.push_back(0);
                    continue;
                }
            }
 
            if(aidx<n){               
                if(k>=a[aidx]){
                    ans.push_back(a[aidx]);
                    aidx++;
 
                    continue;
                }
            }            
            if(bidx<m){
                if(k>=b[bidx]){
                    ans.push_back(b[bidx]);
                    bidx++;
                    continue;
                }
            }    
        }
        if(ans.size()<m+n) puts("-1");
        else{
            for(int a : ans) printf("%d ",a);
            puts("");
        }
    }
    
}

 

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round731-Div.3/ㅊ.cpp