贪心进阶

· · 个人记录

AT_abc137_d

首先这一题不能拿背包写，10^5 的数据，背包至少两重循环， O(n^2)，最大 10^{10}

我们可以想到从前往后填。
而且先贪时间，后贪钱(拿不到工资的贪钱干吗?)。

所以，发现从前往后填是错误的(贪心都贪心不起来)。
那我们能不能从后往前填呢?

我们在第 i + 1 个位置可以填的数，在第 i 个位置一定也能填。
每次找到可以在这里填的数，贪钱即可。

Code

#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
struct node{
    ll a,b;
};
ll n,m,ans;
node a[100005];
priority_queue<ll,vector<ll>,less<ll> > pq;

bool cmp(node a,node b){
    if(a.a == b.a) return a.b > b.b;
    return a.a < b.a;
}

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

AT_abc123_d

Two种代码。
首先 A、B、C 按照从大到小排序。

Mr.蒋

考虑最优情况。
在第 (i,j,k) 位置的和(a[i] + b[j] + c[k]) 在最优情况下一定是第 i \times j \times k 个大的，因为前面的都比他大。
所以如果 i \times j \times k 大于 K 说明最优情况都大于 K
所以就可淘汰掉大量情况。

Mr.陈

先暴力求出 a 和 b 的所有情况
记得排好序
后面的情况一定是建立在这时候的前 \min(K,x \times y) 项，在这个区间内暴力求出即可。

Code

我第一次想到的思路是 Mr.蒋 的，所以我的代码版本也是 Mr.蒋 的

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
priority_queue<ll> pq;
ll x,y,z,m,a[1005],b[1005],c[1005];

bool cmp(ll a,ll b){
    return a > b;
}

int main(){
    cin >> x >> y >> z >> m;
    for(int i = 1;i <= x;i++) cin >> a[i];
    for(int i = 1;i <= y;i++) cin >> b[i];
    for(int i = 1;i <= z;i++) cin >> c[i];
    sort(a + 1,a + 1 + x,cmp);
    sort(b + 1,b + 1 + y,cmp);
    sort(c + 1,c + 1 + z,cmp);
    for(int i = 1;i <= x;i++){
        if(i > m) break;
        for(int j = 1;j <= y;j++){
            if(i * j > m) break;
            for(int k = 1;k <= z;k++){
                if(i * j * k > m) break;
                pq.push(a[i] + b[j] + c[k]);
            }
        }
    }
    for(int i = 1;i <= m;i++){
        cout << pq.top() << "\n";
        pq.pop();
    }
    return 0;
}

P9525

这一题首先就是贪心，贪每科最高分。
但是会有一些情况就不能选


考虑这种情况，正常我们应该选 (x:1,y:2,z:3)
但是 2 的 x 却等于最高分!
题目中有一句话 : 每个成员都有自己的优势，这意味着每个成员都有一项能力值严格大于其他两人的对应能力值。
看到这个 严格大于 没有，这就说明这种情况是非法的。
那我就把 2 给弹出去。
我称这种情况为 多科第一

还是上面这张图，我弹到后面，就出现了以下情况

你发现才被删掉的2又重回最大了！
为了防止这样的情况，我们再拿个 vis 数组标记这个数有没有被删，如果最大被删过了，直接弹出。

这一题由于是动态的，所以用优先队列

结构体优先队列

我以前是这么写的:

 struct node{
    int x,y;
 };
 bool operator < (node a,node b){
     if(a.x == b.x) return b.y < a.y;
     return b.x < a.x;
 }

但老师告诉我，如果结构体多起来，就有点麻烦了。 

 struct node{
    int x,y;
 };
 struct node_2{
    int x,y;
 };
 node :: friend bool operator < (node a,node b){
     if(a.x == b.x) return b.y < a.y;
     return b.x < a.x;
 }

所以我们一般定义在结构体内部 

 struct node{
    int x,y;
    bool operator < (const &b) const{
         if(x == b.x) return b.y < y;
         return b.x < x;
    }
 };
 struct node_2{
    int x,y;
 };

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
struct node{
    ll x,id;
    bool operator < (const node& a) const{
        return a.x > x;
    }
};
priority_queue<node> X,Y,Z;
ll n,x[150005],y[150005],z[150005];
bool vis[1500005];

void work(){
    node a = X.top();
    node b = Y.top();
    node c = Z.top();
    if(vis[a.id] == 1){
        X.pop();
        return ;
    }
    if(vis[b.id] == 1){
        Y.pop();
        return ;
    }
    if(vis[c.id] == 1){
        Z.pop();
        return ;
    }
    if(x[b.id] == a.x){
        Y.pop();
        vis[b.id] = 1;
        return ;
    }
    if(x[c.id] == a.x){
        Z.pop();
        vis[c.id] = 1;
        return ;
    }
    if(y[a.id] == b.x){
        X.pop();
        vis[a.id] = 1;
        return ;
    }
    if(y[c.id] == b.x){
        Z.pop();
        vis[c.id] = 1;
        return ;
    }
    if(z[a.id] == c.x){
        X.pop();
        vis[a.id] = 1;
        return ;
    }
    if(z[b.id] == c.x){
        Y.pop();
        vis[b.id] = 1;
        return ;
    }
    cout << a.x + b.x + c.x << "\n";
    exit(0);
    return ;
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i] >> z[i];
        X.push({x[i],i});
        Y.push({y[i],i});
        Z.push({z[i],i});
    }
    while(X.size() > 0 && Y.size() > 0 && Z.size() > 0) work();
    cout << "-1\n";
    return 0;
}