[关闭]
@Jerusalem 2016-02-14T13:37:40.000000Z 字数 905 阅读 1108

Solution

Vol9


BZOJ1113

首先注意到矩形的宽是没有意义的,于是我们可以认为矩形的宽都是一。

假设第i个矩形,在其之前具有一个矩形j,满足high(i)=high(j)且在[i,j]中没有矩形比它小,则覆盖第i个矩形是不需要额外花费的,因为我们可以用第j个矩形直接拉过去。

如果不存在,则第i个矩形显然需要额外花费。

完成上面算法的最简单手法显然是枚举(当然可以线段树优化)。

继续考察,我们发现假设出现了一个高度为i的矩形,在它之前出现过的高度大于i的都没有意义,这启示我们使用单调栈。

我们从头向尾枚举,维护一个单调栈,栈中存放的是矩形的高度,递增。每当扫描到第i个矩形,我们在单调栈中弹出所有比它高的矩形,之后检查栈顶是否和它等高,如能,则不需额外花费,否则需要额外花费,然后将它压栈。

显然,这个算法的复杂度是均摊O(n)的。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <stack>
  8. using namespace std;
  9. stack<int> Q;
  10. int da[250005];
  11. int n;
  12. void Solve()
  13. {
  14. int ans=1;Q.push(da[1]);
  15. for(int i=2;i<=n;i++){
  16. while(!Q.empty()&&Q.top()>da[i])
  17. Q.pop();
  18. if(Q.empty()||da[i]>Q.top())
  19. ans++;
  20. Q.push(da[i]);
  21. }
  22. printf("%d\n",ans);
  23. }
  24. void Readdata()
  25. {
  26. freopen("loli.in","r",stdin);
  27. scanf("%d",&n);
  28. for(int i=1;i<=n;i++){
  29. int crash;
  30. scanf("%d%d",&crash,&da[i]);
  31. }
  32. }
  33. void Close()
  34. {
  35. fclose(stdin);
  36. fclose(stdout);
  37. }
  38. int main()
  39. {
  40. Readdata();
  41. Solve();
  42. Close();
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注