自动搬运

查看原文

来自洛谷，原作者为

	miemieQWQ **

搬运于2025-08-24 21:33:51，当前版本为作者最后更新于2017-08-28 21:15:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

话说这个题目没题解就算了,连个标签也不给.

起初我以为是区间dp,结果...(中间8点全WA,最后一点还T掉了)

为了对这道题宣泄不满,我祭出随机数大法...(AC两个点...)

其实这道题 模拟+贪心 就好了.

成功的第一步就是认真读题:

注意客人的请求是有序的,不能先s只榨o一种r果汁t!

模拟的话大家都是大佬,我就用队列和集合随便搞搞.

贪心的策略稍微难想一些:

每次遇到 新的果汁 并且 所有榨汁机相对不干净 的时候,

我们选择一个优先级最高的榨汁机清洗(榨汁机刚刚榨过的果汁,需要再次榨的时间越久优先级越高)

举个栗子:

两台榨汁机正在榨: 4 5 (号果汁)

客人还需要: 7 8 5 4 5 (号果汁)

这时我们肯定要清洗 榨4号的机器 来榨7,

再清洗7(因为之后不需要榨7了)来榨8,

榨5不用清洗,榨4清洗8,榨5,over.(清洗3次)

我最怕的就是类似"显而易见"这种话,只要不是水题,我的智商和5岁小孩没有区别.

所以我们来证一下贪心吧:

(以榨汁机刚刚榨果汁的编号作为榨汁机的编号)

设机器刚刚榨过果汁X ={x1,x2...xk},客人还需要果汁Y ={y1,y2...yn}.

若 y1 ∉ X 并且 xa ∉ Y,清洗xa是最优解之一;

若 y1 ∉ X 并且 X ⊆ Y,

令{x1,x2...xk}在Y中 第一次 出现的时间为{t1,t2...tk},

要榨 Y-X 中的果汁肯定要清洗至少一次,就像y1一样

当ta越大时则在Y中xa之前的X的元素越多,即清洗次数越少.

ta最大,Y中xa之前的X中的元素最多(为除开xa的所有X中的元素),

若不清洗xa,则有xb∈X会导致多清洗一次,所以清洗xa最优.

下面我把我的AC代码贴上,仅供参考.

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int k, n, ans = 0;
queue<int> pos[N];    //pos[i].表示要 i号果汁客人的位置 
set<int> machine;    //machine表示当前机器正在榨的果汁 
queue<int> juice;    //表示果汁请求队列 
void arrange(int x)
{
    juice.pop(), pos[x].pop();
    if (machine.find(x) == machine.end()) //如果没有找到合适的榨汁机就要清洗了 
    {
        ans++;
        int farthest = 0, best;
        for (set<int>::iterator it = machine.begin(); it != machine.end(); it++)
            if (pos[*it].empty()) //如果这个果汁之后都没有客人点了,就直接清洗 
            {
                machine.erase(*it), machine.insert(x);
                return ;
            }
            else if (farthest < pos[*it].front()) //找一个短时间不可能用到的榨汁机清洗 
                farthest = pos[*it].front(), best = *it;
        machine.erase(best), machine.insert(x);
    }
    return ;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >>k >>n;
    for (int i = 1, x; i <= n; i++)
    {
        cin >>x;
        pos[x].push(i);    //类似桶排的方法存果汁请求的位置 
        juice.push(x);    //当前请求入队 
    }
    //在不清洗的情况下安排满k个榨汁机 
    while (machine.size() < k && !juice.empty())
    {
        int temp = juice.front();
        juice.pop(), pos[temp].pop();
        machine.insert(temp);
    }
    while (!juice.empty()) //如果还有果汁要榨就给安排榨汁机 
        arrange(juice.front());
    cout <<ans <<endl;
    return 0;
}