题解：P10647 [NordicOI 2023] Ice Cream Machines

· · 题解

题解：P10647 [NordicOI 2023] Ice Cream Machines

题目传送门

引入

首先，我们想要暴力拿 79 分再进行火车头优化，不难想象暴力程序：

码1

用队列处理位置，类似于广搜的思路进行枚举，安排每个机子何时使用，但是时间复杂度劣，为 O(n^2)（sbtk7 TLE）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
int m,k,n,ans=0;
queue<int> pos[MAXN];//使用队列存储冰激凌机子的口味 
bool has[MAXN];
int mac[MAXN],use=0;
int ice[MAXN],where;
void an_pai(int x)
{
    pos[x].pop();//依次弹出判断 
    if(!has[x])
    {
        ans++;
        if(use<k)
        {
            mac[++use]=x;
            has[x]=true;
            return;
        }
        //下面是判断此冰激凌机以后是否使用 
        int far=0,bes;
        for(int i=1;i<=use;i++)
        {
            if(pos[mac[i]].empty())
            {
                has[mac[i]]=false;
                has[x]=true;
                mac[i]=x;
                return;
            }
            else if(far<pos[mac[i]].front())    far=pos[mac[i]].front(),bes=i;
        }
        has[mac[bes]]=false;
        mac[bes]=x; 
        has[x]=true;
        //不处理 
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);//输入 
    for (int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        pos[x].push(i);//压入队列 
        ice[i]=x;//初始化 
    }
    for(where=1;where<=n;where++)   an_pai(ice[where]);//依次判断每个冰激凌机 
    printf("%d",ans);
    return 0;
}

鸣谢： @un1i 指导

优化

看范围， 1 \le n \le 2 \times 10 ^ 5，理想的时间复杂度是 O(n \times log2(n)) 。log2(n) 从何而来？显然有对于贪心的堆优化。这个优化是易证明的，一定清洗最晚有需求的机子。

我们不甘落后，看着堆的标签，灵光一闪，想出 O(n \times log2(n)) 优化策略，实际上与代码 1 大同小异，也是先初始化，再处理时间。不同在于要用 counter 记录状态。

可以用大根堆处理时限，把编号和征用时间压进堆中，进行排序：征用时间靠后者优先，就减少了用于排序的时间复杂度，是一个较好的优化。

码2

有 28 分 WA 代码（sbtk7 AC）：

#include<iostream>
#include<queue>
#define int long long
#define ctn continue
#define I ios::sync_with_stdio(0);
#define AK cin.tie(0);
#define CSP cout.tie(0);
#define endl "\n"
using namespace std;
struct node//定义结构体小根堆 
{
    int a1,b1;
    friend bool operator<(node a,node b)//判断函数 
    {
        if(a.a1!=b.a1)  return a.a1<b.a1;
        return a.b1<b.b1;
    }
};
priority_queue<node> q;//优先队列 
int c[200005],position[200005],xia[200005];
int counter,answer;
bool have[200005];
int n,m,k;
inline void input()//不那么快的快读 
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        xia[i]=n+1;
        cin>>c[i];
    }
}
inline node mp(int x,int y)//不想make_pair 
{
    node zc;
    zc.a1=x,zc.b1=y;
    return zc;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    I AK CSP
    input();
    for(int i=1;i<=n;i++)
    {
        xia[position[c[i]]]=position[c[i]]=i;//初始化 
    }
    for(int i=1;i<=n;i++)
    {
        if(have[c[i]])
        {
            q.push(mp(xia[i],c[i]));
            ctn;
        }
        if(counter==k)
        {
            int linshi=q.top().b1;
            have[linshi]=false;
            q.pop();
            counter-=1;
        }
        q.push(mp(xia[i],c[i]));//压入堆逐个处理，类似于程序 1 
        have[c[i]]=true;
        counter++,answer++;
    }
    cout<<answer<<endl;
    return 0;
}

我们充分发扬人类智慧，使用嫁接之术，特判数据范围，

码3

100 分代码应运而生：

#include<bits/stdc++.h>
#define ctn continue
#define I ios::sync_with_stdio(0);
#define AK cin.tie(0);
#define CSP cout.tie(0);
#define endl "\n"
#define MAXN 200005
using namespace std;
int m,k,n,ans=0;
queue<int> pos[MAXN];
bool has[MAXN];
int mac[MAXN],use=0;
int ice[MAXN],where;
struct node
{
    int a1,b1;
    friend bool operator<(node a,node b)
    {
        if(a.a1!=b.a1)  return a.a1<b.a1;
        return a.b1<b.b1;
    }
};
priority_queue<node> q;
int c[200005],position[200005],xia[200005];
int counter,answer;
bool have[200005];
inline node mp(int x,int y)
{
    node zc;
    zc.a1=x,zc.b1=y;
    return zc;
}
void an_pai(int x)
{
    pos[x].pop();
    if(!has[x])
    {
        ans++;
        if(use<k) 
        {
            mac[++use] = x;
            has[x]=true;
            return;
        }
        int far=0,bes;
        for(int i=1;i<=use;i++)
        {
            if(pos[mac[i]].empty())
            {
                has[mac[i]]=false;
                has[x]=true;
                mac[i]=x;
                return;
            }
            else if(far<pos[mac[i]].front())    far=pos[mac[i]].front(),bes=i;
        }
        has[mac[bes]]=false;
        mac[bes]=x;
        has[x]=true;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(k<=100)
    {
        for(int i=1,x;i<=n;i++)
        {
            scanf("%d",&x);
            pos[x].push(i);
            ice[i]=x;
        }
        for(where=1;where<=n;where++)   an_pai(ice[where]);
        printf("%d",ans);
        return 0;
    }
    else
    {
        I AK CSP
        for(int i=1;i<=n;i++)
        {
            xia[i]=n+1;
            cin>>c[i];
        }
        for(int i=1;i<=n;i++)
        {
            xia[position[c[i]]]=position[c[i]]=i;
        }
        for(int i=1;i<=n;i++)
        {
            if(have[c[i]])
            {
                q.push(mp(xia[i],c[i]));
                ctn;
            }
            if(counter==k)
            {
                int linshi=q.top().b1;
                have[linshi]=false;
                q.pop();
                counter-=1;
            }
            q.push(mp(xia[i],c[i]));
            have[c[i]]=true;
            counter++,answer++;
        }
        cout<<answer<<endl;
        return 0;
    }
}

总结

综上，本篇题解的思维瓶颈和妙处在于人类智慧之嫁接堆优化贪心的策略，减小时间复杂度，防止 TLE 。

望理解望通过 qwq