Description
N個(gè)矩形,排成一排. 現(xiàn)在希望用盡量少的矩形海報(bào)Cover住它們. Input
第一行給出數(shù)字N,代表有N個(gè)矩形.N在[1,250000] 下面N行,每行給出矩形的長與寬.其值在[1,1000000000]2 1/2 Postering Output
最少數(shù)量的海報(bào)數(shù). Sample Input 5
1 2
1 3
2 2
2 5
1 4
解題思路： 單調(diào)棧的水題，維護(hù)一個(gè)遞增的單調(diào)棧，退棧時(shí)如果遇到相等，就代表可以少用一張海報(bào)。
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
