题目传送门:乐团派对 (nowcoder.com)
思路 / Thought
首先对能力值数组进行排序,因为选人的时候顺序没要求,升序的话方便考虑,如果i可以组成乐队的话,比i小的肯定可以组成。
定义dp[i]表示到i为止可以组成的最大合法乐团数量。
接下来就可以写状态转移方程

第i个人,要么分到前面的乐队,要么分到后面的乐队。
但是第N个只能分到前面的乐队,所以输出的答案应该是dp[N - a[N]] + 1。
如果a[N] > N就输出-1。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 9; int a[maxn], dp[maxn];//dp[i] means from 1 to i, the count of teams signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N;cin >> N; for(int i = 1;i <= N; ++ i)cin >> a[i]; sort(a + 1, a + 1 + N);//升序 for(int i = 1;i <= N; ++ i) { dp[i] = dp[i - 1]; if(a[i] <= i)dp[i] = max(dp[i - a[i]] + 1, dp[i - 1]); } if(a[N] <= N)cout << dp[N - a[N]] + 1 << '\n'; else cout << -1 << '\n'; return 0; }
Comments NOTHING