CSES 2. Towers (1073)

출처: 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 )