Algoogle

Algorithm for Programming Contest

AOJ 2547 Carpet

Category: AOJ Tag: greedy

Carpet

問題概要


解法


すべての長方形はy=0に接していると考えていい.
それらの長方形の左上の数を数えればいい.
(与えられた図の左上の角になっている部分をカウントする)
ある高さの入力があったらそれより高さが大きい長方形はそれ以上横に広がれない.

priority_queueを用いる.
毎回の入力aについてaより大きい値はすべてポップする.
もしトップがaじゃなかったらaをプッシュしてカウントする.

コード


(2547.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <queue>

using namespace std;

int main(){

    int n, ans = 0;
    cin >> n;
    priority_queue<int> s;
    while(n--){
        int a;
        cin >> a;
        while(!s.empty() && s.top() > a) s.pop();
        if(s.empty() || s.top() != a){
            s.push(a);
            ans++;
        }
    }
    cout << ans << endl;
}

Comments