題目來源:https://zerojudge.tw/ShowProblem?problemid=b006
內容
給定若干個各種長寬的矩形,請求出最多有多少個矩形可以疊在一起使得上方的矩形其長與寬均不大於下方的矩形。注意,上下矩形的邊必須平行,也就是說矩形可以 90 度旋轉或不旋轉但是不能轉其他角度。
輸入說明
每一行的第一個數字為矩形的個數 n,接著有 2n 個正整數,分別為第一個 矩形的長與寬、第二個矩形的長與寬、…。所有的數字皆以空白間格,數字不大 於 30000。例如下面範例的第一行代表有三個矩形尺寸分別為 1×5、2×3、3×2, 對於此輸入可以有兩個矩形疊在一起。
輸出說明
依序每一行輸出每一個案例所求之值。
範例輸入 #1 範例輸出 #1
3 2
1 5 2 3 3 2 4
5
1 1 4 8 5 6 6 7 7 7
第一、其實這題題目的測資很軟,錯的上傳也會是對的,就像我第一眼看到這程式的時候,我把它誤解成跟b966: 第 3 題 線段覆蓋長度一樣的題目了(點題目可以看到我該題的解法),所以我用pair來裝矩形的兩邊,將長邊都放到pair的first,短邊放到second...。
附上錯誤的程式碼如下:
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; while(cin >> n) { int m = 0; vector<pair<int , int>> vp; while(m++ < n) { int x , y; cin >> x >> y; pair<int , int> p; if(x > y) { p.first = x; p.second = y; } else { p.first = y; p.second = x; } vp.push_back(p); } sort(vp.begin() , vp.end()); int count = 0; int max = 0; for(int i = n-1; i > 0 ; i--) { //cout << "vp[i].second = " << vp[i].second << " vp[i-1].second = " << vp[i-1].second <<" i = " << i << endl;; if(vp[i].second < vp[i-1].second) { if(max < count) max = count; count = 0; } else { if(count == 0) { count = 2; } else count++; } } if(max < count) max = count; cout << max <<endl; } return 0; }
上面的程式問題在於如果面對(5 4)(4 4)(2 7)(2 1)(1 1),程式會判定疊成兩堆分別為(5 4)(4 4)跟(2 7)(2 1)(1 1),但其實正確答案是(5 4)(4 4)(2 1)(1 1 )。
所以建議增加
5
5 5 4 4 2 7 2 1 1 1這組測資還有
7
7 1 6 6 5 2 4 4 3 3 2 2 1 1
以下附上正確的解答:https://programinn.blogspot.com/2020/07/b006.html