hdu 6396 Swordsman

【题目链接】

题目意思

T组案例，每组案例给两个整数n,m，表示n个怪物和m个能力值，下面一行给出人的m个能力值，下面n行，每行给出2m个数字，表示怪物的m个能力值和打败该怪物后，人的各m个能力可以增加的数值，求人最多打败多少个怪物并输出人的各项能力值。

这里吐槽一下题目，必须要加读入挂才能过，不然TLE。

Sample Input
1
4 3
7 1 1
5 5 2 6 3 1
24 1 1 1 2 1
0 4 1 5 1 1
6 0 1 5 3 1
Sample Output
3
23 8 4

Hint

For the sample, initial V = [7, 1, 1]
① kill monster #4 (6, 0, 1), V + [5, 3, 1] = [12, 4, 2]
② kill monster #3 (0, 4, 1), V + [5, 1, 1] = [17, 5, 3]
③ kill monster #1 (5, 5, 2), V + [6, 3, 1] = [23, 8, 4]
After three battles, Lawson are still not able to kill monster #2 (24, 1, 1)
because 23 < 24.

解题思路

将n个怪物的各项能力值全部拿出来排序，然后给m个初值为1的指针，每次移动指针到该项能力值小于怪物的该项能力值为止，然后判断在移动的过程中有没有怪物被杀死，若有，更新人的各项能力值，继续移动指针并重复上述过程（指针不充值），直到在移动指针的时候，没有怪物被杀死，即得答案。
tip:这里讲怪物拆分为了m个小怪物，即当人的各项能力值大于等于m个小怪物的能力值时，怪物才能被杀死。

各数组作用

a[i]数组：怪物i的各项能力值
a[i]数组：杀死怪物i后提升的各项能力值
id[i]数组：所有怪物能力i的值（从小到大排序，并且id[i][j]中存的是该项能力第j小的怪物的编号，并非该项能力值）
que数组：人的各项能力
num数组：判断怪物的几项能力被杀死（当num[i]==m时，该怪物被杀死，更新人的能力值）
point数组：指针

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
int a[200000][6], b[200000][6], id[6][200000], que[6], num[200000], point[6];
int flag;
namespace fastIO {
#define BUF_SIZE 100000
    //fread -> read
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    inline void read(int &x) {
        char ch;
        while (blank(ch = nc()));
        if (IOerror) return;
        for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
#undef BUF_SIZE
};
using namespace fastIO;

int main()
{
    int t;
    read(t);
    while (t--)
    {
        int n, m, ans = 0;
        read(n); read(m);
        //init
        for (int i = 1; i <= m; i++)
            point[i] = 1;
        for (int i = 1; i <= n; i++)
            num[i] = 0;
        //read
        for (int i = 1; i <= m; i++)
            read(que[i]);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
                read(a[i][j]);
            for (int j = 1; j <= m; j++)
                read(b[i][j]);
        }
        //init
        for (int i = 1; i <= m; i++)
        {
            flag = i;
            for (int j = 1; j <= n; j++)
                id[i][j] = j;
            sort(id[i] + 1, id[i] + n + 1, [](int q, int w)
            {
                return a[q][flag] < a[w][flag];
            });
        }
        //main
        while (true)
        {
            int oldans = ans;
            for (int i = 1; i <= m; i++)
            {
                while (point[i] <= n && a[id[i][point[i]]][i] <= que[i])
                {
                    int t = id[i][point[i]];
                    point[i]++;
                    num[t]++;
                    if (num[t] == m)
                    {
                        ans++;
                        for (int j = 1; j <= m; j++)
                            que[j] += b[t][j];
                    }
                }
            }
            if (oldans == ans)
                break;
        }
        printf("%d\n", ans);
        for (int i = 1; i <= m; i++)
            printf("%d%c", que[i], i != m ? ' ' : '\n');
    }
}