[Jzoj] 3792. 分队问题

题目描述

给定n个选手，将他们分成若干只队伍。其中第i个选手要求自己所属的队伍的人数大等于a[i]人。 在满足所有选手的要求的前提下，最大化队伍的总数。 注：每个选手属于且仅属于一支队伍。

题目解析

不能用贪心。 反例： $12455555$ $124[55555]$无解 $[12][455555]$最优解

$DP$ 充分利用“一队的队员都在一个区间内”的性质 满足最后一人即能满足所有人（最后一人的要求$a[]$最高） $f[i]$表示前i名队员最多分成的队伍数量 $f[i]=max(f[j]+1)，j\in [0，i–a[i]]$ 枚举第$i$个人所处的队伍人数

对于这个枚举的$j$，可用前缀和优化： $f[i]=s[i–a[i]]+1$ $s[i]=max(s[i-1],f[i])$

代码

#include<bits/stdc++.h> #define ll long long #define N 1000005 using namespace std; int n,a[N],g[N],f[N],ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) { if(i>=a[i]) f[i]=g[i-a[i]]+1; else f[i]=0; g[i]=max(f[i],g[i-1]); } cout<<f[n]; }