Description
N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们. Input
第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering Output
最少数量的海报数. Sample Input 5
1 2
1 3
2 2
2 5
1 4
解题思路： 单调栈的水题，维护一个递增的单调栈，退栈时如果遇到相等，就代表可以少用一张海报。
#include <bits/stdc++.h>using namespace std;int stk[10000010], top, n, w, h, ans;int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> w >> h; while(h <= stk[top]){ if(h == stk[top]) ans++; top--; } stk[++top] = h; } cout << n - ans << endl; return 0;}新闻热点
疑难解答
