hdu6396 Swordsman（贪心）

Swordsman

题目传送门

解题思路

先将每种属性排序，因为打倒怪兽会使属性增强，所以肯定是能打就打，用cnt[i]记录怪兽i已经被超过的属性数量，如果被超过的属性数为k了，则打倒此怪兽，将获得的属性加成加上，然后继续推进，直到当前所有属性不能再超过新的怪兽属性了。

由于数据量很大，要快读

代码如下

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

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 == '
' || ch == '
' || ch == '	';
    }
    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;

const int N = 100005;

struct T{
    int index, val;
    bool operator<(const T& a)const{
        return val < a.val;
    }
}a[6][N];
int v[6];
int b[N][6];
int record[N];

int main()
{
    int t;
    read(t);
    while(t --){
        int n, k;
        read(n), read(k);
        for(int i = 1; i <= k; ++i)
           read(v[i]);
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= k; ++j)
                read(a[j][i].val), a[j][i].index = i;
            for(int j = 1; j <= k; ++j)
                read(b[i][j]);
        }
        for(int i = 1; i <= k; ++i)
            sort(a[i] + 1, a[i] + n + 1);
        int cnt[6];
        for(int i = 1; i <= k; ++i)
            cnt[i] = 1;
        memset(record, 0, sizeof(record));
        int ans = 0;
        bool flg = true;
        while(flg){
            flg = false;
            for(int i = 1; i <= k; ++i){
                while(cnt[i] <= n && a[i][cnt[i]].val <= v[i]){
                    flg = true;
                    int index = a[i][cnt[i]].index;
                    record[index] ++;
                    if(record[index] == k){
                        ++ans;
                        for(int j = 1; j <= k; ++j)
                            v[j] += b[index][j];
                    }
                    ++cnt[i];
                }
            }
        }
        printf("%d
", ans);
        for(int i = 1; i < k; ++i){
            printf("%d ", v[i]);
        }
        printf("%d
", v[k]);
    }
    return 0;
}