不好做啊……想不出来……看题解……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<iostream> #include<string> #include<algorithm> using namespace std; int n; struct node { int l, w; bool operator < (const node& n2) const { if (l != n2.l)return l > n2.l; if (w != n2.w)return w > n2.w; return false; } }arr[5005]; bool visited[5005]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i].l >> arr[i].w; } sort(arr + 1, arr + n + 1); bool flag = false; int cnter = 0, ptr = 0; do { flag = false; for (ptr=1;ptr <= n; ptr++) { if (!visited[ptr]) { flag = true; visited[ptr] = true; break; } } if (!flag)break; cnter++; for (int i = ptr+1; i <= n; i++) { if (visited[i] || arr[i].l > arr[ptr].l || arr[i].w > arr[ptr].w) continue; visited[i] = true; ptr = i; } } while (flag); cout << cnter; } |