[Codeforces 1148B] Born This Way

[Codeforces 1148B] Born This Way - 1700

문제 설명 : 

A~B, B~C로 가는 비행기 시간표가 있다. 여기서 최대 k개의 비행기편을 취소시켜서 C에 도착하는 시간을 최대한 늦추어야 한다. A~B 소요시간은 ab, B~C 소요시간은 bc이며, 경우에 따라 C에 도착하는 경우가 불가능하게 만들 수도 있다.

풀이 :

경우의 수로 문제를 쪼개서 풀 수 있는 유형이다(이 문제 풀이의 핵심). 총 k개의 항공편을 취소할 수 있으므로 1를 A~B, B~C로 적절하게 분배하여 최대한으로 늦추는 경우를 찾으면 된다. 그래서 A~B 0개 B~C k개, A~B 1개 B~C k-1개....이런 식으로 모든 경우를 조사해 보는 것이 다. 그래서 B에 도착한 시간이 t이라면, t시간 이상일 때 출발하는 B~C 항공편 중에서 가장 작은 편을 탑승하게 된다. 이를 찾는 방법은 바이너리 서치를 이용하면 된다.

주의할 점 : 

n,m이 k보다 작거나 같으면 C에 도착하는 것이 불가능하다.

배운 점 : 

k를 A~B 항공편을 취소하는 경우와 B~C 항공편을 취소하는 편으로 경우의 수를 분배하면 빈틈없이 모든 가능한 경우를 조사해볼 수 있다. 경우의 수로 쪼갤 수 있는 아이디어가 핵심인 문제였다.

코드:

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
priority_queue<int,vector<int>,greater<int>> mpq;
const int SPACE=0,NL=1;  string exm;
inline void showAll(vector<int> &v,int sep){ //0=space,1="\n"
    for(int &here:v) printf("%d%c",here,(sep)?'\n':' '); }
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
/*********************Contest Template***********************/
const int SIZE= 200009;
 
int a[SIZE],b[SIZE];
 
int main(){
    exm="-1";
    int n,m,ab,bc,k;    scanf("%d %d %d %d %d",&n,&m,&ab,&bc,&k);
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&a[i]);
        a[i]+=ab;
    }
    for(int i=1 ; i<=m ; i++)
        scanf("%d",&b[i]);
 
    if(n<=k || m<=k) exf();
 
    int mx=0;
    for(int i=k ; i>=0 ; i--){
        int ff=i,ss=k-i;
        int tgt=a[i+1];
 
        int l=0,r=m+1;
        while(l+1<r){
            int mid=(l+r)/2;
 
            if(b[mid]>=tgt){
                r=mid;
            }
            else l=mid;
        }
        if(r+ss>m) exf();
        mx=max(mx,b[r+ss]);
    }
    printf("%d\n",mx+bc);
 
    return 0;
}
/*

*/