洛谷题单指南-贪心-P4447 [AHOI2018初中组] 分组

标签：P4447 AHOI2018 int 洛谷题 最少 分组 mp 人数 结尾

原题链接：https://www.luogu.com.cn/problem/P4447

题意解读：将一个有序的数列，按不重复连续数分成一组，可分成若干组，使得人数最少的组在各种分组方式之中是最大的。

解题思路：

观察样例说明，有6个测试点的ai​互不相同，因此直接将数据排序，然后连续数分成一组，计算每组数量最少的，即为答案，60分到手。

60分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int a[N], n;
int ans = N;

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    int cnt = 1;
    for(int i = 2; i <= n; i++)
    {
        if(a[i] - a[i-1] != 1)
        {
            ans = min(ans, cnt);
            cnt = 1;
        }
        else cnt++;
    }

    ans = min(ans, cnt);
    cout << ans;
    
    return 0;
}

如何进一步优化？

最关键的问题是实力值数据会出现重复的情况，每个分组都必须连续且不能重复，因此可以采用如下贪心策略：

核心思想是对每一个数，评估应该加入哪个分组，为了使分组人数更加均衡，应该优先加入可以加入的人数最少的分组。

1、先将所有数据由小到大排序

2、对于每一个实力值数据，寻找是否有分组可以加入

3、如果有分组可以加入，则加入该分组；如果有多个分组可以加入，则加入人数最少的分组；否则，创建一个新的分组

4、遍历所有分组，人数最少的即为答案

要实现以上策略，关键的数据结构为

map<int, priority_queue<int, vector<int>, greater<int>> > mp;

 mp存储所有以key结尾的分组人数，使用优先队列是为了方便快速找到人数最少的分组 算法过程描述如下： 1、对实力值由小到大哦排序 2、遍历每一个实力值a   3、判断在mp中是否存在以a-1结尾的分组   4、如果存在则取以a-1结尾的分组最少人数cnt     5、在mp中移除以a-1结尾的最少人数分组     6、在mp中添加以a结尾的人数是cnt+1的分组   7、如果在mp中不存在以a-1结尾的分组     8、在mp中添加以a结尾的人数是1的分组 9、遍历mp，取分组最少的人数

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int a[N], n;
map<int, priority_queue<int, vector<int>, greater<int>> > mp; //key：value，表示以key结尾的所有分组的人数，value是小根堆
int ans = N;

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    for(int i = 1; i <= n; i++)
    {
        if(mp[a[i] - 1].size()) //如果存在分组以a[i] - 1结尾
        {
            int cnt = mp[a[i] - 1].top(); //取以a[i] - 1结尾的分组的最小人数
            mp[a[i] - 1].pop();
            mp[a[i]].push(cnt + 1); //增加一个以a[i]结尾的分组，人数是cnt + 1
        }
        else //如果不存在以a[i] - 1结尾的分组
        {
            mp[a[i]].push(1); //增加一个以a[i]结尾的新分组人数
        }
    }

    for(pair<int, priority_queue<int, vector<int>, greater<int>> > p : mp)
    {
        if(p.second.size())
        {
            ans = min(ans, p.second.top());
        }
    }
    cout << ans;
    
    return 0;
}

 

标签：P4447,AHOI2018,int,洛谷题,最少,分组,mp,人数,结尾
From： https://www.cnblogs.com/jcwy/p/18034912