训练营同学来自n(1≤n≤105)个城市,每个城市的同学人数分别为a1,a2,…,an(1≤an≤109)。小Z将派出n辆车迎接同学。同一个城市的同学需要坐同一辆车,一辆车只能载来自同一个城市的同学,一辆车只能跑一次,且不能超过每辆车的载客量b1,b2, …, bn(1≤bn≤109)。请问有多少种不同的方式把这n个城市的同学安排到这n辆车?
输入的第一行包含n。第二行包含n个空格分隔的整数a1,a2,…,an。第三行包含n个空格分隔的整数b1,b2, …, bn。
输出满足条件的方案数,结果对100000007取模。
#include <bits/stdc++.h> using namespace std; int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif int n; cin >> n; vector<long> people; vector<long> car; const int m = 100000007; for (int i = 0; i < n; i++) { long a; cin >> a; people.push_back(a); } for (int i = 0; i < n; i++) { long a; cin >> a; car.push_back(a); } sort(people.begin(), people.end(), greater<long>()); sort(car.begin(), car.end(), greater<long>()); long ans = 1; for (int i = 0; i < n; i++) { int j = i; while (j < n && car[j] >= people[i]) { j++; } ans *= j - i; ans %= m; if (ans == 0) { break; } } cout << ans; fclose(stdin); fclose(stdout); return 0; }