P4447-分组 - 从萌新到萌新的成长历程

题目传送门

题目思路

类似一个覆盖的问题，有点像积木，统计各个值出现的次数

然后从小到大排列，从最左边的开始选，如果当前的这个数量是比右边的大，那么就停止，比如是1 2 3 3 4.那么肯定是要在3这里停住，拿出分组1 2 3来，然后再3 4 ....的分。

至于证明，显然这是一个最优的子结构

实现略

第一版的代码如下，有问题：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class Node
{
public:
    int v;
    int n;
    Node(int v, int n) : v(v), n(n) {}
};

int main()
{
    vector<Node> q;
    priority_queue<int, vector<int>, greater<int>> fq;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        fq.push(x);
    }
    while (!fq.empty())
    {
        Node n(fq.top(), 1);
        fq.pop();
        while (!fq.empty() && fq.top() == n.v)
        {
            n.n++;
            fq.pop();
        }
        q.push_back(n);
    }
    int ss = q.size();
    q.push_back(Node(0, 0));
    int re = 100000;
    Node a = q[0];
    int str = 0;
    while (str != ss)
    {
        int temp = 1;
        a = q[str];
        while (str != ss)
        {
            if (a.n > 1)
                if (a.n <= q[str + temp].n)
                    q[str + temp - 1].n--;
                else
                {
                    q[str + temp - 1].n--;
                    break;
                }
            if (q[str + temp].v == a.v + 1)
            {
                a = q[str + temp];
                temp++;
            }
            else
                break;
        }
        if (temp < re)
            re = temp;
        while ((str != ss && q[str].n == 1 && q[str].v < a.v) || (q[str].v != q[str + 1].v - 1 && str != ss))
            str++;
    }
    cout << re << endl;
    return 0;
}

问题在哪呢，看样例(从别人的题解那里扒的一个，没想到还真跑出bug了)：

1 2 2 3 3 4 4 5

会输出2，明显不对，因为是1234,2345，应该是4

代码在运行到1234时，退出了，是因为str++的逻辑有问题，应该只跳过1，但是它直接跳到了4

修改方法，最开始的思路有问题，因为分组直接就删掉了这个，所以应该不论是否n>1都应该执行n--操作，n>1改成n>0，因为--之后还大于0的才是需要判断的，最后str++处的n==1条件改成0就好了

于是就AC了

AC代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class Node
{
public:
    int v;
    int n;
    Node(int v, int n) : v(v), n(n) {}
};

int main()
{
    vector<Node> q;
    priority_queue<int, vector<int>, greater<int>> fq;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        fq.push(x);
    }
    while (!fq.empty())
    {
        Node n(fq.top(), 1);
        fq.pop();
        while (!fq.empty() && fq.top() == n.v)
        {
            n.n++;
            fq.pop();
        }
        q.push_back(n);
    }
    int ss = q.size();
    q.push_back(Node(0, 0));
    int re = 100000;
    Node a = q[0];
    int str = 0;
    while (str != ss)
    {
        int temp = 1;
        a = q[str];
        while (str != ss)
        {
            q[str + temp - 1].n--;
            if (a.n > 0)
                if (!(a.n <= q[str + temp].n))
                    break;
            if (q[str + temp].v == a.v + 1)
            {
                a = q[str + temp];
                temp++;
            }
            else
                break;
        }
        if (temp < re)
            re = temp;
        while ((str != ss && q[str].n == 0 && q[str].v < a.v) || (q[str].v != q[str + 1].v - 1 && str != ss))
            str++;
    }
    cout << re << endl;
    return 0;
}