魔塔

Posted on Edited on In

题目大意：把 问 题 再 抽 象 一 下 就 是 ， 勇 士 有 K 个 属 性 ， 大 小 分 别 为v[1],v[2],…,v[K]，一共有 N 只怪物，每只怪物也有相应的 K 个属性，第 i 只怪 物 的 第 j 项 属 性 标 记 为 \(a[i][j]\) 。 若 对 于 任 意 的 j （ 1≤j≤K ） 都 有a[i][j]≤v[j]，则勇士可以干掉第 i 只怪物，而且干掉第 i 只怪物后，勇士的各项属性都会得到提升，其中第 j 项属性的提升了 b[i][j]。现在小 Z 好奇，按照最优策略来打怪，最多能干掉多少只怪物（n属于1e5）

我不会贪心，我写的暴力，但是我A了

对于k等于1的情况，特判

对于k不等于1的情况，就直接搞，我常数小，就只是700ms就过了，其实可以把我卡成\(o(n^2)\)的

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 66;

int n, i, j, k, pd, res;
int me[7], a[N][7], b[N][7], vis[N];

struct yhzhyhm
{
    int f, g;
    bool operator < (const yhzhyhm &x) const
    {
        return f < x.f;
    }
}yh[N];

inline void yhm_clear()
{
    res = 0;
    memset(me, 0, sizeof me);
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    memset(vis, 0, sizeof vis);
    memset(&yh, 0, sizeof yh);
    return;
}

inline void yh_func()
{
    me[1] = read();
    for (i = 1; i <= n; ++ i) yh[i].f = read(), yh[i].g = read();
    sort(yh + 1, yh + 1 + n);
    for (i = 1; i <= n; ++ i)
    {
        if (me[1] >= yh[i].f)
        {
            me[1] += yh[i].g;
            ++ res;
        }
    }

    put(res), put(me[1]);

    return;
}

inline void yhm_func()
{
    n = read(), k = read();
    if (k == 1) return (void)(yh_func());
    for (i = 1; i <= k; ++ i) me[i] = read();
    for (i = 1; i <= n; ++ i)
    {
        int num = 0;
        for (j = 1; j <= k; ++ j) a[i][j] = read();
        for (j = 1; j <= k; ++ j) b[i][j] = read();
    }

    do{
        pd = 0;
        for (i = 1; i <= n; ++ i)
        {
            if (vis[i]) continue;
            int num = 0;
            for (j = 1; j <= k; ++ j) if (me[j] >= a[i][j]) ++ num;
            if (num == k)
            {
                for (j = 1; j <= k; ++ j) me[j] += b[i][j];
                ++ res;
                vis[i] = 1;
                pd = 1;
            }
        }
    }while (pd == 1);

    put(res);
    for (i = 1; i <= k; ++ i) putf(me[i]);
    puts("");
    return;
}

signed main()
{
    int T = read();

    while (T --) 
    {
        yhm_clear();
        yhm_func();
    }
    
    return 0;
}

补：

正解， 此题有性质：k很小

所以我们可以开k个小根堆，分别把每一维都扔进去，现比较第一维，如果发现第一维合适，再比较第二维，以此类推

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> >q[5];

int a[N][5],b[N][5],v[5];

int main()
{
    while(T --)
    {
        shuru;
        for(int i=0;i<m;i++) while(!q[i].empty()) q[i].pop();
        for (int i=0;i<m;i++) IO::read(v[i]);
        for (int i=1;i<=n;i++)
        {
            for (int j=0;j<m;j++) IO::read(a[i][j]);
            for (int j=0;j<m;j++) IO::read(b[i][j]);
            q[0].push(P(a[i][0],i));
        }
        int p=0,ans=0;
        while(1)
        {
            for (int i=0;i<m-1;i++)
            {
                while(!q[i].empty() && q[i].top().first<=v[i])
                {
                    int x=q[i].top().second; q[i].pop();
                    q[i+1].push(P(a[x][i+1],x));
                }
            }
            while (!q[m-1].empty() && q[m-1].top().first<=v[m-1])
            {
                ans++;
                int x=q[m-1].top().second; q[m-1].pop();
                for (int i=0;i<m;i++) v[i]+=b[x][i];
            }
            if (p==ans) break;
            p=ans;
        }
        shuchu;
    }
    return 0;
}