@Jerusalem
2016-02-14T21:37:40.000000Z
字数 905
阅读 1377
Solution
首先注意到矩形的宽是没有意义的,于是我们可以认为矩形的宽都是一。
假设第i个矩形,在其之前具有一个矩形j,满足high(i)=high(j)且在[i,j]中没有矩形比它小,则覆盖第i个矩形是不需要额外花费的,因为我们可以用第j个矩形直接拉过去。
如果不存在,则第i个矩形显然需要额外花费。
完成上面算法的最简单手法显然是枚举(当然可以线段树优化)。
继续考察,我们发现假设出现了一个高度为i的矩形,在它之前出现过的高度大于i的都没有意义,这启示我们使用单调栈。
我们从头向尾枚举,维护一个单调栈,栈中存放的是矩形的高度,递增。每当扫描到第i个矩形,我们在单调栈中弹出所有比它高的矩形,之后检查栈顶是否和它等高,如能,则不需额外花费,否则需要额外花费,然后将它压栈。
显然,这个算法的复杂度是均摊O(n)的。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
stack<int> Q;
int da[250005];
int n;
void Solve()
{
int ans=1;Q.push(da[1]);
for(int i=2;i<=n;i++){
while(!Q.empty()&&Q.top()>da[i])
Q.pop();
if(Q.empty()||da[i]>Q.top())
ans++;
Q.push(da[i]);
}
printf("%d\n",ans);
}
void Readdata()
{
freopen("loli.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int crash;
scanf("%d%d",&crash,&da[i]);
}
}
void Close()
{
fclose(stdin);
fclose(stdout);
}
int main()
{
Readdata();
Solve();
Close();
return 0;
}