Swordsman

题目连接

[HDU 6396] 2018 Multi-University Training Contest 7--1011 Swordsman

题解

中档题,提议大概是某人是一个剑士要打怪。剑士和怪物均有不同的属性,只有当剑士的所有属性均不低于怪物的对应属性时剑士才可以将怪物干掉。击杀怪物将获得一定的经验值,具体表现为每一种属性均可以获得怪物该属性经验值所对应的增长。求剑士最多可以击杀的怪物数量以及击杀之后的各项属性值。

首先注意到至多只有五项属性。我们将怪物的每个属性单独进行排序。之后重复以下过程:将当前属性小于剑士的怪物计数加一,将所有计数达到属性数量的怪物击毙并基于勇者经验值。直到所有怪物均被击杀或者无法击杀新的怪物。总的时间复杂度为O(knlogn+nk)。

注意需要使用读入挂,不然绝对会超时。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*fronthead,*fronttail;
inline char GET_CHAR(){
    if(fronthead==fronttail){
        int l=fread(buffer,1,BufferSize,stdin);
        fronttail=(fronthead=buffer)+l;
        if(fronthead==fronttail)return EOF;
    }
    return *fronthead++;
}
inline int READ(){
    int x=0,f=1;char c=GET_CHAR();
    for(;!isdigit(c);c=GET_CHAR()){
        if(c==EOF)return EOF;
        if(c=='-')f=-1;
    }
    for(;isdigit(c);c=GET_CHAR())x=(((x<<2)+x)<<1)+c-'0';
    return x*f;
}
const int maxn = 100005;
const int INF = 2147483647;
int n,k,q1;
int v[6],pos[6];
int b[maxn][6];
int num[maxn];
pair<int,int> sorta[6][maxn];
int ans;
inline void read() {
    ans=0;
    n=READ(),k=READ();
    for (int i=1;i<=k;i++){
        v[i]=READ();
        pos[i]=0;
        sorta[i][n+1].first=INF;
    }
    for (int i=1;i<=n;i++){
        num[i]=0;
        for (int j=1;j<=k;j++){
            sorta[j][i].first=READ();
            sorta[j][i].second=i;
        }
        for (int j=1;j<=k;j++){
            b[i][j]=READ();
        }
    }
    for (int i=1;i<=k;i++){
        sort(sorta[i]+1,sorta[i]+1+n);
    }
}

inline bool slove() {
    bool flag= true;
    while(flag){
        flag=false;
        for (int i=1;i<=k;i++){
            while(sorta[i][pos[i]+1].first<=v[i]){
                pos[i]++;
                num[q1=sorta[i][pos[i]].second]++;
                if (num[q1]==k){
                    ans++;
                    flag=true;
                    for (int j=1;j<=k;j++){
                        v[j]+=b[q1][j];
                    }
                }
            }
        }
    }
}

int _;
int main() {
    _=READ();
    while (_--) {
        read();
        slove();
        printf("%d\n",ans);
        for (int i=1;i<=k;i++){
            printf("%d%c",v[i],(i==k?'\n':' '));
        }
    }
    return 0;
}

标签: implementation, sortings

添加新评论