[BOJ/C+]#1946新入社員

👀問題を解く

書類の成績と面接の成績のどちらも他のすべての社員より順位が高いため、書類の成績を基準に昇順に並べ、面接の成績を計算します.

👀イニシャルコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

    int T;
    cin>>T;
    while(T){
        int N;
        vector<pair<int,int>> score; // (서류, 면접)
        cin>>N;
        int cnt=N;
        for(int i=0;i<N;i++){
            int a,b; cin>>a>>b;
            score.push_back(make_pair(a,b));
        }

        sort(score.begin(), score.end()); // 서류 순위순으로 정렬

        for(int i=N-1;i>=0;i--){
            for(int j=i-1;j>=0;j--){ // 서류 꼴지부터, 그 윗 순위들의 면접점수를 봄
                // 서류는 이미 다른 지원자보다 낮음
                // 면접이 다른 모든 앞 지원자보다 커야 함
                int interviewScore=score[i].second;
                if(interviewScore>score[j].second) {
                    cnt--;
                    break;
                }
            }
        }

        cout<<cnt;
        T--;
    }
}

昇順に並び、下位の社員から上位の社員をカウントダウンして2ドアを回ったところ、시간초과と間違えた.

👀コードの改良

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

    int T;
    cin>>T;
    for(int t=0;t<T;t++){
        int N;
        vector<pair<int,int>> score; // (서류, 면접)
        cin>>N;

        for(int i=0;i<N;i++){
            int a,b; cin>>a>>b;
            score.push_back(make_pair(a,b));
        }

        sort(score.begin(), score.end()); // 서류 순위순으로 정렬

        int cnt=1;
        int interviewScore=score[0].second; //1위의 면접 점수

        // 그 뒤에부턴, 면접 점수가 무조건 더 높아야 채용
        for(int i=1;i<N;i++){
            if(score[i].second<interviewScore){
                cnt++;
            }
            // 제일 높은 순위로 업데이트
            interviewScore=min(score[i].second, interviewScore);
        }

        cout<<cnt<<"\n";
    }

    return 0;
}

ファイル成績を基準に並べ替えられているため、ゼロインデックスからファイル成績が上位にランクされています.
そのため、1つのインデックスから~N-1まで、순위가 높은 지원자の中で最も高い面接順位よりも面接成績が高い.
そのため、最高位の面接成績を更新し続けます.