有N个士兵，第i个士兵的重量是w[i]。
有N匹马，第i匹马的重量是h[i]。
现在为每个士兵分配一匹马。
1个士兵和1匹马在一起，就组成了一个骑士。
骑士的战斗力等于士兵的重量和马的重量的乘积。
第1个士兵的身份是班长，为了显示班长的地位，
班长所在的骑士的战斗力必须比其他骑士的战斗力要大。
你是司令，你的任务是为这N个士兵分配马，
那么你有多少种不同的分配方案可以满足上述的要求？
答案模1000000007。
第一行，一个整数N。2 <= N <= 2000。
第二行，N个整数，第i个整数是w[i]。 1 <= w[i] <= 1000。
第三行，N个整数，第i个整数是h[i]。 1 <= h[i] <= 1000。
一个整数。
输入：
4
5 8 4 8
19 40 25 20
输出：
2
输入：
3
10 2 10
100 150 200
输出：
3
我们读一下题目，有N匹马和N个人，每个人对应一匹马，则该个人的战斗力为马的战斗力*人的战斗力。现1号人是班长，问有几种对应方法使得班长的战斗力是N个人中最高。
数据大小是N<=2000，显然，我们要选一种O(n²)的解法。
我们不知道班长对应哪匹马，所以我们要枚举班长对应哪匹马，这将会用掉一个n。
所以我们的题目变成了：有N匹马和N个人，每个人对应一匹马，则该个人的战斗力为马的战斗力*人的战斗力，问有多少种方法使得每个人战斗力不超过k。
我们要将马和人一一对应，这样我们发现需要O(n²)的时间，这会超时！！
我们再仔细看，假如第i个人和第j个人战斗力w[i]<w[j]，且第l匹马战斗力h[l]，
如果w[i]*h[l]>k，则w[j]*h[l]>k.
反之，如果w[j]*h[l]<k，则w[i]*h[l]<k。
我们发现是有单调性的，即弱的人可以选的马会比强的人可以选的马多，且强的人可以选的马，弱的人同样可以选。
所以我们把马从小到大排，把人从大到小排。
所以我们可以只按马去枚举，然后从强的人开始选，假如不行就可以换次强接着往下看（因为强的人选的次强同样可以选），以此类推。
假如说最强的人可以选sum[1]匹，次强的人可以选sum[2]匹，……最弱的人可以选sum[N-1]匹。
则方案数为sum[1]*(sum[2]-1)*……*(sum[N-1]-N+2)。
因为强的人选走了一匹，且必定会出现在后面的人可以选的方案，所以要减去强的人选走的一匹，后面的人以此类推。
至此，我们完成了在O(n)的时间内求出了：有N匹马和N个人，每个人对应一匹马，则该个人的战斗力为马的战斗力*人的战斗力，问有多少种方法使得每个人战斗力不超过k。
我们枚举班长的马，最终答案就是全部加起来，加法原理。
#include<bits/stdc++.h>
using namespace std;
long long N,w[2005],h[2005],FH,ans,sum,g,k;
int main(){
scanf("%lld",&N);
for(int i=1;i<=N;i++){
scanf("%lld",&w[i]);
}
for(int i=1;i<=N;i++){
scanf("%lld",&h[i]);
}
sort(w+2,w+1+N);
sort(h+1,h+1+N);
for(int i=1;i<=N;i++){
FH=h[i]*w[1];
sum=1;g=N;k=0;
for(int j=1;j<=N;j++){
if(i==j)continue;
while(w[g]*h[j]>=FH){
sum*=(k-N+g);
sum%=1000000007;
g--;
if(g==1)break;
}
k++;
if(g==1)break;
}
while(g!=1){
sum*=(k-N+g);
sum%=1000000007;
g--;
}
if(sum<=0)continue;
ans+=sum;
ans%=1000000007;
}
printf("%lld\n",ans);
return 0;
}
原文：https://www.cnblogs.com/Kiana-Kaslana/p/12402342.html