Skip to content

11044: 【原1044】二哥打游戏

题目

题目描述

author: zyz 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1044

Description

二哥打即时战略游戏是个菜鸟,他从来不考虑什么时候该干啥,他只做一件事:选中建筑,然后开始造单位。

二哥可以生产 K 种不同的单位,当然每种单位都需要消耗一定的资源。在这个游戏中资源只有两种:食物和木材。每一秒开始,二哥的农民都会往基地送一定数量的某种资源,而在资源送到的那个时刻,二哥就看他能否用当前的资源造出一个单位,只要可以他就会造。如果有不同的单位都可以被生产出来,二哥一定会造最厉害的单位。于是二哥还给这 K 种单位各标记了一个等级,等级越高,该单位在他眼中就越有价值。

在这个游戏里,同一时刻基地获得的资源都算作一整份,而资源总是被整份地使用掉。譬如某时刻二哥获得了 20 的食物,造一个单位要 15 的食物,那么这 20 单位的食物一定会一起被消耗掉。另一个特别的地方在于,先获得的资源总是先被使用。譬如二哥前两秒依次获得了 10, 15 单位的食物,而造某个单位消耗 15 食物,那么实际一定是消耗了前两秒产生的 25 单位的食物,而不会只使用第二秒产生的 15 食物。食物和木材互不影响,即不会因为使用了木材而浪费在其之前生产出来的食物,也不会因为使用了食物而浪费在其之前生产出来的木材。

最后,如果二哥生产了一个农民(farmer),那么他将获得资源奖励,今后每一秒送到基地的资源的数量都要+1。资源奖励可以无限叠加,即如果当前生产了 n 个农民,那么资源奖励就是+n。

给出一局游戏中每一秒送到基地的资源,请你告诉二哥他生产了哪些单位,以及游戏结束时剩余的资源量。至于游戏的输赢,你们懂的。

Input Format

第 1 行:一个整数 K 表示有多少种不同的单位。

第 2..K+1 行:每行先给一个长度不超过 20 的英文字母组成的字符串,表示该单位的名称。接下来给出三个整数 a, b, l 分别表示该单位的食物消耗、木材消耗和等级。没有任何两个单位具有相同的名称或等级。单位的名称对大小写敏感。农民单位始终被称为"farmer"。

第 K+2 行:一个整数 N 表示游戏的持续时间。

第 K+3..K+N+2 行:按时间顺序给出每一秒送到基地的资源类型和数量。资源类型以一个 "food" 或 "wood" 的字符串表示,后面跟着一个整数为资源数量。

Output Format

每制造一个单位,输出一行:"#X: a XXX was created.",其中 X 表示该单位制造出来的时间,从 1 开始计时;XXX 表示该单位的名称。无需考虑英语中 a 和 an 的正确使用。

最后输出一行: "food: XX, wood: XX" ,其中 XX 为每种资源最后的剩余量。

Hint

对100%的数据,2 <= K <= 10, 3 <= N <= 10000。

题目中出现的所有数(除了N以外)均为不超过 1000 的非负整数。

Sample Input

3
farmer 5 0 1
footman 16 0 2
tank 10 35 3
5
food 5
food 15
wood 40
food 20
wood 16

Sample Output

#1: a farmer was created.
#2: a footman was created.
#4: a tank was created.
food: 0, wood: 17

FineArtz's solution

/* 二哥打游戏 */
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

class Unit{
public:
    char name[25];
    int food = 0, wood = 0, priority = 0;

    bool operator <(const Unit &u){
        return priority > u.priority;
    }
};

int main(){
    Unit a[15];
    int k, n;
    cin >> k;
    for (int i = 1; i <= k; ++i){
        cin >> a[i].name >> a[i].food >> a[i].wood >> a[i].priority;
    }
    sort(a + 1, a + k + 1);
//    for (int i = 1; i <= k; ++i)
//        cout << a[i].name << ' ' << a[i].food << ' ' << a[i].wood << ' ' << a[i].priority << endl;
    int wood = 0, food = 0, bonus = 0;
    int wq[10005], fq[10005], wfront = 0, wrear = 0, ffront = 0, frear = 0;
    cin >> n;
    for (int t = 1; t <= n; ++t){
        char source[5];
        int amount;
        cin >> source >> amount;
        amount += bonus;
        if (source[0] == 'f'){
            fq[frear++] = amount;
            food += amount;
        }
        else if (source[0] == 'w'){
            wq[wrear++] = amount;
            wood += amount;
        }
        for (int i = 1; i <= k; ++i){
            if (food >= a[i].food && wood >= a[i].wood){
                cout << "#" << t << ": a " << a[i].name << " was created." << '\n';
                int f = 0, w = 0;
                while (f < a[i].food){
                    f += fq[ffront++];
                }
                food -= f;
                while (w < a[i].wood){
                    w += wq[wfront++];
                }
                wood -= w;
                if (strcmp(a[i].name, "farmer") == 0)
                    ++bonus;
            }
        }
    }
    cout << "food: " << food << ", wood: " << wood << '\n';
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int SIZE = 10010;

struct Unit {
    char name[25];
    int food, wood, level;
} units[11];
int unitNumber, timeNumber;
int food[SIZE], wood[SIZE], farmer = 0, resource, foodStart = 0, woodStart = 0, foodEnd = 0, woodEnd = 0, totalFood = 0, totalWood = 0;
char type[5];

bool cmp(const Unit &unit1, const Unit &unit2) {
    return unit1.level < unit2.level;
}

int main() {
    scanf("%d", &unitNumber);
    for(int i = 0; i < unitNumber; ++i)
        scanf("%s%d%d%d", &units[i].name, &units[i].food, &units[i].wood, &units[i].level);
    sort(units, units + unitNumber, cmp);
    scanf("%d", &timeNumber);
    for(int i = 1; i <= timeNumber; ++i) {
        scanf("%s%d", &type, &resource);
        resource += farmer;
        if(type[0] == 'f'){
            totalFood += resource;
            food[foodEnd++] = resource;
        }
        else if(type[0] == 'w'){
            totalWood += resource;
            wood[woodEnd++] = resource;
        }
        for(int j = unitNumber - 1; j >= 0; --j)
            if(units[j].food <= totalFood && units[j].wood <= totalWood){
                for(int remainFood = units[j].food; remainFood > 0; remainFood -= food[foodStart], totalFood -= food[foodStart++]);
                for(int remainWood = units[j].wood; remainWood > 0; remainWood -= wood[woodStart], totalWood -= wood[woodStart++]);
                if(!strcmp(units[j].name, "farmer"))
                    ++farmer;
                printf("#%d: a %s was created.\n", i, units[j].name);
                break;
            }
    }
    printf("food: %d, wood: %d\n", totalFood, totalWood);
    return 0
}