算法总结——贪心2

· · 算法·理论

贪心是应用于那些只需要做出在当前看来是最好的选择就能获得整体最好结果的问题上，这篇文章将讲解更加复杂的贪心题。

T1 [ABC137D] Summer Vacation

思路：

这题我们需要贪心贪两个东西，一个是延迟时间，一个是工资。\ 越靠前的日子就尽量选择延迟时间长的任务，因为可以把延迟时间短的留给后面的日子去做，这样可以尽量多的做可以在限定时间内领到工资的任务。在这些可以选的任务中，每天（如果可以做的话）都选择工资最高的。\ 但如果按照上面的思路直接实现的话，会很麻烦，因为不方便选择当前日做的任务，我们可以反着来实现。\ 我们用一个 for 循环从小到大枚举距离结束的天数，在每次循环中，将当前新增（因为剩余天数增加的）的可以做的任务的工资压入一个大根堆中，压入完成之后，如果堆不为空（其实就是当前还有没有可以做的任务）那么累加器加上堆顶（做这个任务），再弹出堆顶（以后都不能做这个任务了）。

代码：

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

struct node {long long a,b;} a[100005];
long long n,m;
priority_queue<long long>pq;

bool cmp(node x,node y) {return x.a < y.a;}

int main(void)
{
    cin >> n >> m;
    for(long long i = 1;i <= n;i++) cin >> a[i].a >> a[i].b;
    sort(a+1,a+n+1,cmp);
    long long pt = 1,cnt = 0;
    for(int i = 1;i <= m;i++)
    {
        while(pt <= n && a[pt].a == i)
        {
            pq.push(a[pt].b);
            pt++;
        }
        if(pq.size())
        {
            cnt += pq.top();
            pq.pop();
        }
    }
    cout << cnt;
    return 0;
}

T2 [ABC123D] Cake 123

思路：

突破口往往在小范围的数据上，一看数据范围： 1 \le K \le \min(3000,X\times Y\times Z) 。这就是突破口。\ 三个序列直接排出前 K 名比较麻烦，但先将两个序列的所有组合合成一个序列再和第三个序列进行组合就简单很多，这就是本题的正解。\ 我们可以先把 A 序列和 B 序列的的所有配对情况全部暴力枚举出来，记为 AB，再排个序，这时候，我们只需要将序列 AB 的前 K 项和序列 C 配对，再排个序，这时候，前 K 项就是答案。

代码

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

long long n1,n2,n3,K,a1[1005],a2[1005],a3[1005],a12[1000005],ans[3000005];

bool cmp(long long x,long long y) {return x > y;}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n1 >> n2 >> n3 >> K;
    for(int i = 1;i <= n1;i++) cin >> a1[i];
    for(int i = 1;i <= n2;i++) cin >> a2[i];
    for(int i = 1;i <= n3;i++) cin >> a3[i];
    int pt = 0;
    for(int i = 1;i <= n1;i++)
    {
        for(int j = 1;j <= n2;j++)
        {
            a12[++pt] = a1[i]+a2[j];
        }
    }
    sort(a12+1,a12+pt+1,cmp);
    pt = 0;
    for(int i = 1;i <= min(n1*n2,K);i++)
    {
        for(int j = 1;j <= n3;j++)
        {
            ans[++pt] = a12[i]+a3[j];
        }
    }
    sort(ans+1,ans+pt+1,cmp);
    for(int i = 1;i <= K;i++) cout << ans[i] << '\n';
    return 0;
}

T3 [JOISC2022] 团队竞技

这题主循环要写九个 if ，判掉九种非法情况！

思路：

开三个大根堆，分别用来查询三种能力的佼佼者，堆顶表示在堆中这方面最厉害的海狸的编号和该方面的实力。\ 接着就是主循环里要判断的九种情况，一个判对了说明这个答案非法，如果一个都没判对，那么它就是答案。\ 设 x 为 X 的堆顶， y 为 Y 的堆顶， z 为 Z 的堆顶。

之前爆 0 几发就是因为判错了一个条件。

代码：

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

struct node{long long x,id;};
bool operator < (node x,node y) {return x.x < y.x;}

priority_queue<node>qx,qy,qz;

long long n,x[150005],y[150005],z[150005];
bool vis[150005];

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(long long i = 1;i <= n;i++)
    {
        cin >> x[i] >> y[i] >> z[i];
        qx.push({x[i],i});
        qy.push({y[i],i});
        qz.push({z[i],i});
    }
    while(qx.size() && qy.size() && qz.size())
    {
        node a = qx.top(),b = qy.top(),c = qz.top();
        if(vis[a.id])
        {
            qx.pop();
            continue;
        }
        if(vis[b.id])
        {
            qy.pop();
            continue;
        }
        if(vis[c.id])
        {
            qz.pop();
            continue;
        }
        if(x[b.id] == a.x)
        {
            vis[b.id] = 1;
            qy.pop();
            continue;
        }
        if(x[c.id] == a.x)
        {
            vis[c.id] = 1;
            qz.pop();
            continue;
        }
        if(y[a.id] == b.x)
        {
            vis[a.id] = 1;
            qx.pop();
            continue;
        }
        if(y[c.id] == b.x)
        {
            vis[c.id] = 1;
            qz.pop();
            continue;
        }
        if(z[a.id] == c.x)
        {
            vis[a.id] = 1;
            qx.pop();
            continue;
        }
        if(z[b.id] == c.x)
        {
            vis[b.id] = 1;
            qy.pop();
            continue;
        }
        cout << a.x+b.x+c.x;
        return 0;
    }
    cout << -1;
    return 0;
}