【难度】

$3/10$
鄙人不才，WA了8发。。

【题意】

你有 $n$ 个人，**每个人有能力值 $a_i$ ，表示该人所在的队伍人数必须大于等于 $a_i$ **

保证每个人都被分进一个队的情况下，队伍数量最多是多少？无解输出 $-1$ 。

【数据范围】

$0\le n\le 10^5$
$1\le a_i\le 10^9$

【样例输入】

$n$
$a_1 ,a_2,\cdots,a_n$

4
2 1 2 1

【样例输出】

【解释】

队伍1：第一个人、第三个人
队伍2：第二个人
队伍3：第三个人

【思路】

（一）首先考虑贪心

首先判断可行性。易得，若 $\max\{a_i\}>n$ 则无解，输出 $-1$ 。
接下来，人怎么分组？
既然是贪心，易想到我们需要对能力值进行排序。 $\color{green}首先为了防止歧义，这里先对能力数组进行升序处理$

（1）逆序贪心？

【做法】
我们把 $i$ 从 $n$ 到 $1$ 进行循环遍历。
若对于第 $i$ 个人能力值为 $a_i$ 是接下里还没分好组的人。
接下来，我们选择 $i-a[i]+1\sim i$ ，把这些人组成一支队伍。
若 $i-a[i]+1\ge1$ ，则可以划分队伍，因为易得 $\forall k\in[i-a[i]+1,i]，a[k]\le a[i]$
若 $i-a[i]+1<1$ ，则无法划分队伍，就把他们合并到人数最多的队伍。

【结果】
可以AC

$【但是】$
有反例可以 $\color{red}Hack$
比如 $n=12,a[]=\{6,6,6,6,6,6,6,1,1,1,1,1\}$
按照该贪心算法，分组为 $\{6,6,6,6,6,6\;\Big|\;6,1,1,1,1,1\}$ ，为两组。
但是正确的分组应该为 $\{6,6,6,6,6,6,6\;\Big|\;1\;\Big|\;1\;\Big|\;1\;\Big|\;1\;\Big|\;1\}$ ，为六组。
~~牛客数据水了~~

【结论】 $\color{green}该算法并不正确。$

（2）顺序贪心？

【做法】
我们把 $i$ 从 $1$ 到 $n$ 进行循环遍历。
若对于第 $i$ 个人能力值为 $a_i$ 是接下里还没分好组的人。
接下来，我们选择 $i\sim i+a[i]-1$ ，把这些人组成一支队伍。
若 $i+a[i]-1>n$ ，则无法划分队伍，就把他们合并到人数最多的队伍。

【结果】 $92.86分$

$【但是】$
该算法 $\color{red}{非常错误}$ 。 $\forall k\in[i,i+a[i]-1]，a[k]\le a[i]$ 当然不一定成立。
比如分组 $\{2,3,3,4,5\}$
按该算法的分组为 $\{2,3\;\Big|\;3,4,5\}$ ，为两组。但是分组不满足题目要求呀！
但是正确的分组应该为 $\{2,3,3,4,5\}$ ，为一组。

【结论】 $\color{green}{该算法并不正确。}$

（3）改良顺序贪心？

【做法】
我们把 $i$ 从 $1$ 到 $n$ 进行循环遍历。
若对于第 $i$ 个人能力值为 $a_i$ 是接下里还没分好组的人。
接下来，我们选择 $i\sim i+a[i]-1$ ，把这些人组成一支队伍。
若 $a[i+a[i]-1]>a[i]$ ，我们继续选择 $a[i+a[i]-1]-a[i]个人$
直到第一个合法的 $k$ 满足 $\underset{p=i}{\overset{k}{\max}}\{a_p\}=a[k]>k-i+1$
若找不到合法的 $k$ ，则这些人与最大人数的队伍合并。

$【但是】$
该算法 $\color{red}{有点问题}$ 。
比如分组 $\{1,1,2,2,5\}$
按该算法， $i$ 枚举到 $4$ 时，目前分组为 $\{1\;\Big|\;1\;\Big|\;2,2\;\}$ 。
但是遇到 $5$ ，我无法选出5个人来，也无法在某个已有团队中直接把这个人给塞进去。
我们还要再计算最少数目的已有团队，使得团队总人数 $s\ge a_i-1$
怎么变成背包问题了？？这可是贪心做法！

【结论】 $\color{green}{该算法并不优秀。}$

（4）正解贪心

【做法】

升序排序后，**我们先把 $a_n$ 安排掉**，易得至少要 $a_n$ 个人。
我们安排 $\pmb{[n-a[n]+1,n]}$ 这些下标的人： $\forall k\in[n-a[n]+1,n]，a[k]\le a[n]$ 成立，所以该选择一定是合法的、最贪心的。

接下来，我们把 $i$ 从 $1$ 到 $n-a[n]$ 进行循环遍历。与做法3的贪心选择相同：

若对于第 $i$ 个人能力值为 $a_i$ 是接下里还没分好组的人。
接下来，我们选择 $i\sim i+a[i]-1$ ，把这些人组成一支队伍。
若 $a[i+a[i]-1]>a[i]$ ，我们继续选择 $a[i+a[i]-1]-a[i]个人$
直到第一个合法的 $k$ 满足 $\underset{p=i}{\overset{k}{\max}}\{a_p\}=a[k]\le k-i+1$
若找不到合法的 $k$ ，则这些人与最大人数的队伍合并。

$\color{red}{注意：这时的“最大人数的队伍”我们已经选择完毕，该合并一定合法}$

【核心代码】

时间复杂度： $O(N\log N + N)$
就是排序+for循环的时间复杂度。

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e5+50;
int aa[MAX];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
    sort(aa+1,aa+1+n);
    int ren = 1;            /// ren表示目前该队伍中有多少人，默认值为 1
    int ans = 1;
    if(aa[n] > n)printf("-1");
    else{
        for(int i=1;i<=n - aa[n];++i){
            while(i<=n - aa[n] && ren < aa[i]){
                int cha = aa[i] - ren;
                ren += cha;
                i += cha;
            }
            if(i > n - aa[n])break;    /// 找不到合法的‘k’，与最大队伍合并，答案不变
            ans++;            /// 找到了合法的‘k’，新的队伍产生
            ren = 1;
        }
        printf("%d",ans);
    }
    return 0;
}

（二）其次考虑DP做法

$\color{green}{定义 dp[i]表示到第 i个人位置，最大合法队伍的数量为 dp[i]}$

首先，我们一样升序排序。
对于第 $i$ 个人我们可以把它合并在第 $i-1$ 个人的团队里面（如果存在的话）。
或者，我们**选择 $[i-a[i]+1,i]$ 下标的人拉成新的一个队伍**。
当然这时我们 $dp$ 选择的是 $dp[i-a[i]+1-1]$ ，稍微想一想就能得到了。

那么状态转移方程就得到了： $dp[i] = \max \begin{cases} dp[i-1]\\ dp[i-a[i]]+1\qquad 如果i-a[i]+1存在 \end{cases}$

$\color{red}{补充修改：最后的答案应该选择dp[n]=dp[n-a[n]]+1}\\ \color{red}{这是为了保证合法性的考虑}$
【感谢热心网友的Hack！】

【核心代码】

时间复杂度： $O(N\log N + N)$
就是排序+for循环的时间复杂度。
~~人的本质是复读机~~

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 2e5+50;
int aa[MAX];
int dp[MAX];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
    sort(aa+1,aa+1+n);
    int t;
    for(int i=1;i<=n;++i){
        int di = (i - aa[i]);
        t = 0;                        /// 选 [di+1,i]的人的时候的dp[i]的值
        if(di >= 0)t = dp[di] + 1;
        dp[i] = max(t,dp[i-1]);       /// 向左合并
    }
    printf("%d",t==0 ? -1 : t);       /// 为了保证合法，最后一支队伍要选择区间[n-a[n]+1,n]的范围
    return 0;
}

【牛客小白月赛27：贪心 | DP |（详解）】B：乐团的派对

【难度】

【题意】

【数据范围】

【样例输入】

【样例输出】

【解释】

【思路】

（一）首先考虑贪心

（1）逆序贪心？

（2）顺序贪心？

（3）改良顺序贪心？

（4）正解贪心

【核心代码】

（二）其次考虑DP做法

【核心代码】