C语言链表 Attack

淡淡的烟草味﹌ 2022-06-01 10:26 157阅读 0赞

### Attack ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

PBH 最近在玩一个游戏。游戏中玩家有 100 的血量，目前有 n 个小怪，小怪会按顺序前来攻击玩家且小怪只会采用 1v1 的方式，玩家每次可秒杀一个小怪，并受到小怪攻击力的伤害（血量减少小怪攻击力的数值），打死小怪会掉落药水。

现在问题来了，打完这 n 个小怪最少需要喝多少瓶药水（喝药水不耗时）？

#### Input ####

先输入一个整数 t 表示数据的组数，t 不超过 1000。

对于每组数据，第一行先输入小怪的个数 n (1 <= n <= 100)，接下来的 n 行输入小怪攻击力 atki (1 <= atki <= 50) 以及小怪掉落 mi (0 <= mi <= 4) 个药水和药水所能恢复生命的值 ai (1 <= ai <= 30)。

#### Output ####

对于每组数据先输出 "Case \#x: "，x 表示当前为第几组数据，之后输出打完所有小怪需要的最少药水数。如果无法杀死这 n 个小怪，即某次攻击小怪时已无药水可用且当前血量无法攻击小怪（小怪攻击大于等于当前血量），则输出 ”QAQ”。

所有输出均不包括引号。

#### Example Input ####

3
    2
    50 1 20
    49 0
    4
    50 1 10
    40 0
    30 3 20 30 20
    10 0
    3
    50 3 20 15 1
    45 2 1 1
    27 0

#### Example Output ####

Case #1: 0
    Case #2: QAQ
    Case #3: 2

#include <stdio.h>
    #include <stdlib.h>
    struct sdut
    {
        int data;
        struct sdut *next;
    };
    int main()
    {
        int t, n, atki, count = 0, mi, number;
        scanf("%d", &t);
        while(t--)
        {
            number = 0;
            struct sdut *head, *p, *q, *tail;
            int blood = 100;
            count++;
            scanf("%d", &n);
            head = (struct sdut*) malloc (sizeof(struct sdut));
            head -> next = NULL;
            int flag = 1;
            while(n--)
            {
                scanf("%d", &atki);
                if(blood > atki)
                    blood -= atki;
                else
                {
                    tail = head;
                    while(blood <= atki)
                    {
                        if(q)
                        {
                            q = head -> next;
                            blood += q -> data;
                            tail -> next = q -> next;
                            q = q -> next;
                            number++;
                        }
                        else
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(blood > atki)
                    {
                        blood -= atki;
                    }
                }
                scanf("%d", &mi);
                while(mi--)
                {
                    q = head;
                    p = (struct sdut*) malloc (sizeof(struct sdut));
                    scanf("%d", &p -> data);
                    while(q -> next)
                    {
                        if(q -> next -> data > p -> data)
                            q = q -> next;
                        else
                            break;
                    }
                    p -> next = q -> next;
                    q -> next = p;
                }
            }
           if(flag == 1)
           {
               printf("Case #%d: %d\n", count, number);
           }
           else
           {
               printf("Case #%d: QAQ\n", count);
           }
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2378/pid/3879.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2378/pid/3879.html