[Algorithm] 파라메트릭서치 - Parametric Search Problem

해당 문제는 X일에 각각의 붕어빵 기계가 작동된 날로부터의 Score를 계산하는 문제였다.

해당 문제는 파라메트릭 탐색(Parametric Search)라는 생소한 탐색을 사용함으로써 접근이 쉽지 않았다.

해당코드는 아래에 있다.

 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
#define MAX 100100
using namespace std;
 
typedef struct{
    int p;
    int Elec[3];
}FishM; //FishBread Machine
 
FishM Input;
 
long long result;
int T,N,M,K;
int EE[3], DD;
vector <int> DayList[MAX];
 
 
int ParaSearch(int left, int right);
int ElecSearch(int e, int left, int right, int Paramid, int min, int addr);
int proc();
int main(){
    //freopen("input.txt", "r", stdin);
    setbuf(stdout,NULL);
    scanf("%d", &T);
    for(int i=1;i<=T;i++){
        scanf("%d%d%d",&N,&M,&K); //붕어빵기계, 발전기, 기간
 
        proc();//with input
 
        printf("#%d %lld\n", i, result%100000123);
        for(int j=0;j<=MAX;j++){
            DayList[j].clear();
        }
        result=0;
    }
}
 
int proc(){
    //input
    for(int i=1;i<=K;i++){
        int e;
        scanf("%d",&e);
        DayList[e].push_back(i);
    }
    for(int i=1;i<=N;i++){
        scanf("%d%d%d%d", &Input.Elec[0], &Input.Elec[1], &Input.Elec[2], &Input.p);
        int size = DayList[Input.Elec[0]].size() + DayList[Input.Elec[1]].size() + DayList[Input.Elec[2]].size();
        if( size > Input.p){
            ParaSearch(Input.p, K);
        }
        else if(size == Input.p){
            long long MaxDay=0;
            for(int j=0;j<3;j++){
                if(DayList[Input.Elec[j]].size() != 0 && MaxDay < DayList[Input.Elec[j]].back()){
                    MaxDay = DayList[Input.Elec[j]].back();
                }
            }
            result += (MaxDay+K)*(K-MaxDay+1)/2;
        }
    }
    return 0;
}
 
int ParaSearch(int l, int r){
    int left = l;
    int right = r;    
    for(;;){
        int mid = (left+right)/2;
        for(int i=0;i<3;i++){
            EE[i]=0;
            if(DayList[Input.Elec[i]].size() != 0 && DayList[Input.Elec[i]][0] <= mid){
                ElecSearch(Input.Elec[i], 0, DayList[Input.Elec[i]].size()-1, mid, MAX, i);
            }
        }
        int temp = EE[0]+EE[1]+EE[2];
        if(temp == Input.p){
            long long MaxDay=0;
            if(DayList[Input.Elec[0]].size() != 0 && MaxDay < DayList[Input.Elec[0]][EE[0]-1]){
                MaxDay = DayList[Input.Elec[0]][EE[0]-1];
            }
            if(DayList[Input.Elec[1]].size() != 0 && MaxDay < DayList[Input.Elec[1]][EE[1]-1]){
                MaxDay = DayList[Input.Elec[1]][EE[1]-1];
            }
            if(DayList[Input.Elec[2]].size() != 0 && MaxDay < DayList[Input.Elec[2]][EE[2]-1]){
                MaxDay = DayList[Input.Elec[2]][EE[2]-1];
            }
            result += (MaxDay+K)*(K-MaxDay+1)/2;
            return 0;
        }
        else if(temp > Input.p){
            if(left >= right) return 0;
            right = mid-1;
        }
        else if(temp < Input.p){
            if(left >= right) return 0;
            left = mid+1;
        }
    }
    return 0;
}
int ElecSearch(int e, int l, int r, int Paramid, int min, int addr){
    int left = l;
    int right = r;
    for(;;){
        int mid = (left+right)/2;
        if(DayList[e][mid] <= Paramid){
            if(min > (Paramid - DayList[e][mid])){
                min = (Paramid - DayList[e][mid]);
                EE[addr] = mid+1;
                if(left >= right) return 0;
                left = mid+1;
            }
            else{
                if(left >= right) return 0;
                right = mid-1;
            }
            continue;
        }
        else if(DayList[e][mid] > Paramid){
            if(left >= right) return 0;
            right = mid-1;
            continue;
        }
    }
    return 0;
}