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

문제 설명

You have to process n tasks. Each task has a duration and a deadline, and you will process the tasks in some order one after another. Your reward for a task is d−f where d is its deadline and f is your finishing time. (The starting time is 0, and you have to process all tasks even if a task would yield negative reward.)

What is your maximum reward if you act optimally?

입력 

The first input line has an integer n: the number of tasks.

After this, there are n lines that describe the tasks. Each line has two integers a and d: the duration and deadline of the task.

출력

Print one integer: the maximum reward.

입력 예

3
6 10
8 15
5 12

출력 예

2

제약조건

  • 1 <= n  <= 2x10^5
  • 1 <= a,d  <= 10^6

문제 풀이 

입력받은 업무를 필요 시간을 기준으로 정렬한다.

일은 같이 진행할 수 없기 때문에 전체 업무를 끝내는 시간은 필요 시간 전체의 합으로 고정되어 있으므로, 보상이 큰 일을 먼저 하도록 한다. 필요시간이 짧은 순서로 보상을 계산하기 위해서, 처음부터 진행한 시간과 보상을 기록해서 출력한다.

프로그램 내용

더보기 
...
    vector <pair <int, int> > t_list;

    for (int idx = 0; idx < nTask; idx++)
        t_list.push_back({t_start, t_end});

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

    long reward = 0, t_now=0;

    for (int idx = 0; idx < nTask; idx++)
        reward += t_list[idx].second - (t_list[idx].first + t_now);
        t_now += t_list[idx].first;
...

 

Sorting and Searching ( link )

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

'CSES' 카테고리의 다른 글

CSES 2. Room Allocation (1164)  (0) 2019.10.01
CSES 2. Traffic Lights (1163)  (0) 2019.10.01
CSES 2. Towers (1073)  (0) 2019.09.28
CSES 2. Playlist (1141)  (0) 2019.09.28
CSES 2. Stick Lengths (1074)  (0) 2019.09.26

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

문제 설명

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, or begin a new tower. What is the minimum possible number of towers?

입력 

The first input line contains an integer n: the number of cubes.

The next line contains n integers k_1,k_2,…,k_n: the sizes of the cubes.

출력

Print one integer: the minimum number of towers.

입력 예

5
3 8 2 1 5

출력 예

2

제약조건

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

문제 풀이 

몇개의 탑이 있고, 그 마지막값이 얼마인지 검색하는 문제이다.

입력받은 블럭의 크기보다 마지막 값이 큰 탑이 있는지 검색하고, 있으면 새로운 블럭 크기로 바꾸고, 없으면 새로운 탑을 만든다. 입력이 끝나면, 탑의 수를 출력한다.

프로그램 내용

더보기 
...
    multiset <long> tower;

	cin >> temp;
	auto it = tower.lower_bound(temp+1);
	if ( it == tower.end()) 		/// need new tower
    	tower.insert(temp);
	else		/// replace top value
		tower.erase(it);
		tower.insert(temp);
...

 

Sorting and Searching ( link )

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

'CSES' 카테고리의 다른 글

CSES 2. Traffic Lights (1163)  (0) 2019.10.01
CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28
CSES 2. Playlist (1141)  (0) 2019.09.28
CSES 2. Stick Lengths (1074)  (0) 2019.09.26
CSES 2. Maximum Subarray Sum (1643)  (0) 2019.09.26

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

문제 설명

You are given a playlist of a radio station since its establishment. The playlist has a total of n songs.

What is the longest sequence of successive songs where each song is unique?

입력

The first input line contains an integer n: the number of songs.

The next line has n integers k)1,k_2,…,k_n: the id number of each song.

출력 

Print the length of the longest sequence of unique songs.

입력 예

8
1 2 1 3 2 7 4 2

출력 예

5

제약조건

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

문제 풀이 내용

입력받은 노래 목록을 set에 저장하며 중복목록을 확인한다. 중복목록이 나오면, 중복목록이 나오기 전에 있는 목록들을 지운다. 

노래 목록이 끝나면, set의 크기를 출력한다.

프로그램 내용

더보기 
...
    long num_array[nSong] = {0};

    for (int idx = 0; idx < nSong; idx++)
        cin >> num_array[idx];

    set <int> slist;

    int id=0, idx=0;
    int sCount=0;

    while (idx < nSong)
        if ( slist.count(num_array[idx]))
            sCount = max(sCount, idx-id);
            while( num_array[id] != num_array[idx])
                slist.erase(num_array[id]);
                id++;
            id++;
        else
            slist.insert(num_array[idx]);
        idx++;

        sCount = max(sCount, idx-id);
...

 

Sorting and Searching ( link )

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

'CSES' 카테고리의 다른 글

CSES 2. Tasks and Deadlines (1630)  (0) 2019.09.28
CSES 2. Towers (1073)  (0) 2019.09.28
CSES 2. Stick Lengths (1074)  (0) 2019.09.26
CSES 2. Maximum Subarray Sum (1643)  (0) 2019.09.26
CSES 2. Sum of Two Values (1640)  (0) 2019.09.26

+ Recent posts

티스토리툴바