显然如果n个矩形的高度如果都不相同，那么一定要n张海报才能覆盖。出现更优解的当且仅当出现了高度相同的矩形。可以考虑从左边第一个矩形开始，覆盖所有不比它矮的矩形部分，剩下的依次。如果这个矩形已经被完全覆盖了（也就是有一个可达该矩形，并且高度和相同的矩形），那么海报数量不用+1，否则都得+1。
考虑用单调栈维护，从栈底到栈顶单调递增。每次一个矩形的高度x进栈的时候，先维护单调栈的性质，如果发现维护后的栈顶和当前一样高，则不用多一张海报，否则入栈、海报+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /**************************************************************
Problem: 1113
User: abcdabcd987
Language: C++
Result: Accepted
Time:1444 ms
Memory:1792 kb
****************************************************************/
#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
int n,ans;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for (int i=0,x,y;i<n;++i) {
cin>>x>>y;
while (!s.empty() && s.top()>y) s.pop();
if (s.empty() || s.top()!=y) {
++ans;
s.push(y);
}
}
cout<<ans;
}
|
