题解 P2062 【分队问题】

· · 题解

更多的dp题目练习点这里

首先看到这道题第一想法应该是贪心

这个贪心写法应该也很容易写，排序一遍，然后直接选就可以了

信心满满地提交，会发现WA掉前面两个点

这个贪心想法其实有一个很明显的错误

来一组数据

4

2 3 3 3

贪心做法会输出2，但实际上应该输出1

所以这个贪心的想法是必须cut掉的，因为它没有考虑到分队时剩下来的人的a[i]对于队伍人数的限制

至于为什么还能水80分？应该是数据水吧

顺便说一下这是我校某次测评的题目啊，当时就写了这个贪心，然后挂的挺惨的

那么来想想dp做法

设f[i]表示前i个人能够分成的最大的队伍个数

从小到大排序一遍之后，显然可以发现，当第i个人可以加入这个队伍时，当且仅当

i>=a[i]

所以可以得到一个转移方程：f[i]=max(f[k])+1(0<i<=a[i])

但是这样对于百万级别的n是会超时的

考虑怎么去优化它

我们可以开一个数组来储存f[1...n]的最大值

则转移方程可以改成：f[i]=g[i-a[i]]+1

对于g数组的维护：g[i]=max(g[i-1],f[i])

这样就可以完成O(n)转移

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define il inline 
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void print(ll x){if(x<0)putchar('-');x=abs(x);if(x>9)print(x/10);putchar(x%10+'0');}
il void writeln(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
il void write(ll x){if(x<0)putchar('-');x=abs(x);print(x);putchar(' ');}
using namespace std;
/*===================Header Template=====================*/
#define N 1000100
ll n,a[N],f[N],g[N];
int main(){
    read(n);
    for(ll i=1;i<=n;i++)read(a[i]);
    sort(a+1,a+n+1);
    for(ll i=1;i<=n;i++){
        if(i>=a[i])f[i]=g[i-a[i]]+1;
        g[i]=max(f[i],g[i-1]);
    }
    writeln(f[n]);
    return 0;
}