题解 P4447 【[AHOI2018初中组]分组】

RainbOwO · 2020-04-07 23:41:00 · 题解

STL栈+暴力解决此题

我看有好多大佬用队列和二分来解决此题

其间穿插各种结构体与重载

但是用栈来写感觉整道题来说更简洁易懂

适合启发刚开始没有思路的同学

首先要将每一组都想象成一个栈

我们可以利用栈后进先出的特点

若数据与栈顶相比满足条件，则将其压入作为新的栈顶

因为题目要求一个组内元素必须连续

则入栈条件为

st[j].top()+1==a[i]

注意，前面需要在输出后排序以确保按顺序进行入栈操作

如果满足条件，则入栈，否则建立一个新栈，也就是一个新组

最后遍历时取最小值即可

有一个比较重要的点，就是如果多个栈满足条件，则应该选择建立顺序偏后的栈，因为元素数量会更少一些。

最后附上AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
stack<int> st[maxn];
int a[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    int top=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int flag=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=top;j>0;j--)
        {
            if(st[j].top()+1==a[i])
            {
                st[j].push(a[i]);
                flag=1;
                break;
            }
                else flag=0;
        }
        if(flag==0)
        st[++top].push(a[i]);

    }
    int minn=(1<<31)-1;
    for(int i=1;i<=top;i++)
    {
        int temp=st[i].size();
        minn=min(minn,temp);
    }
    printf("%d\n",minn);
    return 0;
}

另，如果有一些同学是直接遍历一遍数组，满足条件就计数，否则更新最小值这一思路，遇到相同元素的时候会有问题，因为不满足条件的会直接跳过，而不会在之后应用他