算法1
(贪心) $O(n)$
牛棚选牛,对于一个高度的牛棚,低与等于他的牛它都能选,
按牛棚从小到大排序,高度最低的牛棚先选,
低牛棚如果后选,高牛棚把它的牛都选了,它就没得选,
而如果有答案,的话低牛棚先选后,高牛棚还是有可选的 ;
时间复杂度
C++ 代码
#include<bits/stdc++.h>
using namespace std ;
int n , a[22] , b[22] ;
int main()
{
cin >> n ;
for( int i = 0 ; i < n ; i ++ ) cin >> a[i] ;
for( int i = 0 ; i < n ; i ++ ) cin >> b[i] ;
sort(a, a + n) , sort(b , b + n) ;
a[n] = 1e9 + 10 ;
long long ans = 1 ;
for( int i = 0 ; i < n ; i ++ )
{
// j 表示比b[i] 这个牛棚低的牛的数量
int j = upper_bound(a , a + n + 1, b[i]) - a ;
// i 是当前已经选的牛棚数量
// t 是 当前牛能选的数量
int t = j - i;
ans = ans * t ;
}
cout << ans ;
return 0 ;
}