[CF 898D] Alarm Clock

[CF 898D] Alarm Clock - 1700

문제 설명 : 

n개의 알람이 울리는 시간이 주어진다. 알람이 연속된 m분의 시간동안 k개 이상 울려서는 안된다. 이 조건을 만족시키기 위해서 꺼야하는 알람의 최소 개수를 구하여라. 

풀이 : 

선택한 구간에서 가장 작은 시간을 t_s라고 한다면 [t_s , t_s+m)구간에 포함되는 시간이 k개 미만이어야 한다. 이를 구현하기 위해서 자료구조 deque를 사용할 것이다. 우선 알람 시각들을 오름차순으로 정렬한다. 그 다음 시각들을 훑으면서 deque에 push_back한다. 그러면 deque의 front에는 먼저 들어간 시각이 들어 있으므로 작은 수가, back에는 나중에 들어간 시각이므로 큰 수가 들어있게 된다. 그래서 back-front의 값이 m보다 커질 때까지, 즉 while(back-front<=m)을 만족할 때 까지 pop_front를 해준다. 이렇게 해준 뒤의 deque의 size가 k이상이면 문제의 조건에 위배된다는 것이므로 알람을 꺼야한다는 의미이다. 이럴 때는 pop_back을 해주고 이는 방금 추가했던 알람 시각을 삭제한다는 의미이다.

주의할 점 : 

-

배운 점 : 

-

코드 :

#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 arr[SIZE];
 
int main(){
    int n,m,k;  scanf("%d %d %d",&n,&m,&k);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
    }
    sort(arr+1,arr+1+n);
 
    int ans=0;
    deque<int> dq;
    for(int i=1 ; i<=n ; i++){
        dq.push_back(arr[i]);
        while(dq.back()-dq.front()>=m) dq.pop_front();
        if(dq.size()>=k){ans++; dq.pop_back();}   
    }
    printf("%d\n",ans);
 
    return 0;
}
/*

*/