출처: https://cses.fi/problemset/task/1632

문제 설명

In a movie festival, n movies will be shown.  movie club consists of k members, who will be all attending the festival.

You know the starting and ending time of each movie. What is the maximum total number of movies the club members can watch entirely if they act optimally?

입력 

The first input line has two integers n and k: the number of movies and club members.

After this, there are n lines that describe the movies. Each line has two integers aa and bb: the starting and ending time of a movie.

출력

Print one integer: the maximum total number of movies.

입력 예

5 2
1 5
8 10
3 6
2 5
6 9

출력 예

4

제약조건

  • 1 <= k <= n <= 2x10^5
  • 1 <= a <= b <= 10^9

문제 풀이 내용

입력받은 영화 시작시간과 끝나는 시간을 이용해서, (영화시간, 시작/끝, 영화순서) 를 영화시간을 기준으로 정렬한다. 영화시작시간이면 클럽 맴버를 보내고, 끝나는 시간이면 본 영화수를 증가시키고, 영화 보고 있는 클럽 맴버수를 감소 시킨다.  

프로그램 내용

더보기 
...
    vector <tuple<int, int>> m_time;

    for(int idx=0; idx < n_movie; ++idx)
        cin >> start_time >> end_time ;
        m_time.push_back({end_time, start_time});

    sort(m_time.begin(), m_time.end(), greater<tuple<int, int>>());

    vector<tuple<int, bool, int>> m_schedule(2*n_movie);

    for (int idx = 0; idx < n_movie; ++idx)
        tie(end_time, start_time) = m_time[idx];
        m_schedule[2*idx] = {start_time, 0, idx};
        m_schedule[2*idx + 1] = {end_time, 1, idx};

    sort(m_schedule.begin(), m_schedule.end());

    set <int> c_movie;
    int ct_member=0;
    int ct_movie=0;

    for (int idx=0; idx < 2*n_movie; ++idx)
        int m_time, m_idx;
        bool flag;
        tie(m_time,flag,m_idx) = m_schedule[idx];

        if(!flag) /// flag == 0, movie start time -> club member see
            c_movie.insert(m_idx);
            ct_member++;
        else if( c_movie.count(m_idx)) /// movie end,
            c_movie.erase(m_idx);
            ct_member--;
            ct_movie++;

        if ( idx < 2*n_movie -1 && get<0>(m_schedule[idx+1]) == m_time)
            continue;

        if (ct_member > n_member) /// can not exceed max member
            c_movie.erase(c_movie.begin());
            ct_member--;
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1660

문제 설명

Given an array of n positive integers, your task is to count the number of subarrays having sum x.

입력  

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a_1,a_2,…,a_n: the contents of the array.

출력  

Print one integer: the required number of subarrays.

입력 예

5 7
2 4 1 2 7

출력 예

3

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= x, a_i <= 10^9

문제 풀이 내용

배열의 값들을 더해가다가, 원하는 값보다 크거나 같아지면 제일 앞쪽 값을 삭제한다. 이때 값이 같은 경우 카운터를 기록해서 출력한다.  

프로그램 내용

더보기 
...
    vector <int> num_arr(nNum);

    int ar_count = 0;
    int ids=0;
    int ar_sum = 0;
    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr[idx] =  temp;
        ar_sum += num_arr[idx];
        while(ar_sum >= tSum)
            if (ar_sum == tSum) ar_count++;
            ar_sum -= num_arr[ids++];
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02

출처: https://cses.fi/problemset/task/1645

문제 설명

Given an array of n integers, your task is to find for each array position the nearest position to its left having a smaller value.

입력 

The first input line has an integer n: the size of the array.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력

Print n integers: for each array position the nearest position with a smaller value. If there is no such position, print 0.

입력 예

8
2 5 1 4 8 3 2 5

출력 예

0 1 0 3 4 3 3 7

제약조건

  • 1 <= n <= 2x10^5 
  • 1 <= x_i <= 10^9

문제 풀이 내용

stack에 작은 값의 위치를 기록한다. 기록된 작은 값의 위치의 값과 새로운 입력을 비교해서 작으면 위치를 출력한다. 새로운 입력의 값이 가장 지금까지 입력중에 가장 작으면 0, 아니면 기록하는 위치를 갱신한다. 출력하는 값은 배열 값이 아니라, 배열 위치이므로 출력할때는 +1을 해준다.

프로그램 내용

더보기 
...
    vector <long> in_num;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    stack<int, vector<int>> num_stack;

    for(int idx = 0 ; idx < nNum; ++idx) 
        while(!num_stack.empty() && in_num[num_stack.top()] >= in_num[idx]) 
            num_stack.pop();

        if(num_stack.empty()) 
            cout << "0 " ; 
        else 
            cout << num_stack.top()+1 << " ";

        num_stack.push(idx);
...

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Sum of Four Values (1642)  (0) 2019.10.02
CSES 2. Sum of Three Values (1641)  (0) 2019.10.02
CSES 2. Reading Books (1632)  (0) 2019.10.02

+ Recent posts

티스토리툴바