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;}新聞熱點
疑難解答
