您的位置:首页 > 游戏 > 手游 > 怎么制作小程序教程_世界新冠肺炎疫情最新情况_西安seo网络优化公司_网站优化策划书

怎么制作小程序教程_世界新冠肺炎疫情最新情况_西安seo网络优化公司_网站优化策划书

2025/3/15 5:32:57 来源:https://blog.csdn.net/2401_82408565/article/details/145065559  浏览:    关键词:怎么制作小程序教程_世界新冠肺炎疫情最新情况_西安seo网络优化公司_网站优化策划书
怎么制作小程序教程_世界新冠肺炎疫情最新情况_西安seo网络优化公司_网站优化策划书

问题描述

在蓝桥王国,国王统治着一支由n 个小队组成的强大军队。每个小队都由相同职业的士兵组成。具体地,第i 个小队包含了 bi名职业为ai的士兵。近日,国王计划在王宫广场举行一场盛大的士兵检阅仪式,以庆祝王国的繁荣昌盛。然而,在士兵们入场的过程中,一场突如其来的风暴打乱了他们的行列,使得不同小队的士兵混杂在一起,次序乱成一团,尽管国王无法知道每个士兵的具体职业,但为了确保仪式能顺利进行,国王打算从这些混乱的士兵中选出一部分,组成k 个“纯职业小组”进行检阅。一个“纯职业小组”定义为由3 名同职业的士兵组成的队伍。请问,国王至少需要选择多少名士兵,才能确保这些士兵可以组成 k 个“纯职业小组”。

输入格式

输入包含多组数据。 第一行包含一个整数 T,表示有T 组数据。对于每组数据:第一行包含两个nt和k,表示小队的数量和要组成的纯职业小组的数量。接下来的 nt行,每行包含两个整数 ai和bi,表示第i 个小队中士兵的职业和数量。

输出格式

对于每组数据,输出一个整数,表示为了组成k 个“纯职业小组”,国王至少需要选择的士兵数量。如果无论如何也无法组成 k 个“纯职业小组”,则输出 −1

样例输入

2

3 2

1 3

2 3

3 3

3 5

1 3

2 3

3 3

样例输出

8

-1

样例说明

在第一个样例中,要想组成2 个“纯职业小组”,国王至少需要选择 8 名士兵。若只选择了 7 名士兵,则这7 名士兵的职业可能为1,1,1,2,2,3,3,无法组成2 个“纯职业小组”。

在第二个样例中,即使选择了所有士兵,也无法组成 5 个“纯职业小组”,因此输出 −1

思路讲解:

程序需要处理多组数据,每组数据包含小队数量 n 和要组成的纯职业小组数量 k,以及每个小队的职业和士兵数量信息。对于每组数据,程序会计算出最少需要选取多少士兵才能满足组成 k 个 “纯职业小组” 的要求,如果无法满足则输出 -1。

具体设计思路

  1. 哈希表的实现

    • 由于 C 语言没有内置的 unordered_map 这样方便的哈希表容器,因此使用自定义的哈希表结构来存储数据。
    • Node 结构体:包含 key(职业)、value(士兵数量)和 next 指针,用于解决哈希冲突,通过链表法将具有相同哈希索引的元素链接在一起。
    • createNode 函数:创建一个新的 Node 节点,为节点分配内存并进行初始化,若内存分配失败会输出错误信息并终止程序。
    • insert 函数:根据键(职业)的哈希值找到在哈希表中的位置,如果该位置为空,将新节点插入此处;若不为空,则将新节点添加到链表的末尾。
    • find 函数:根据键的哈希值找到在哈希表中的位置,然后遍历链表查找节点,若找到则返回该节点,否则返回 NULL
    • freeHashTable 函数:释放哈希表占用的内存,防止内存泄漏,遍历哈希表的每个位置,释放每个位置上的链表节点。
  2. 主函数部分

    • 首先,程序读取测试数据的组数 T
    • 对于每组数据:
      • 读取 n(小队数量)和 k(纯职业小组数量),并将 k 减 1,这可能是为了后续计算的便利性。
      • 创建哈希表 arr 存储每个小队的信息,使用 calloc 函数分配内存,将内存初始化为 0。
      • 读取每个小队的信息,使用 find 函数查找是否已经存在该职业的节点,如果不存在则使用 insert 函数插入新节点,如果已存在则更新该节点的士兵数量。
      • 初始化 ret 为 0,用于存储最终结果(已选士兵数量),hash 数组用于存储处理后的余数信息(如士兵数量除以 3 的余数)。
      • 遍历哈希表,处理每个小队的士兵数量:
        • 对于士兵数量 b 小于 3 的小队,将其士兵数量累加到 ret 中。
        • 对于士兵数量 b 大于等于 3 的小队,先将 ret 加 2,然后将 b 减 2。接着计算 b 除以 3 的商和余数,将商累加到 hash[3] 中,余数对应的 hash 位置加 1。
      • 处理 k - 1 个队伍的情况:
        • 从 i = 3 开始,逐步减小 i,检查 hash[i] 与 k 的大小关系。
        • 如果 hash[i] 小于 k,将 i * hash[i] 累加到 ret 中,将 hash[i] 置为 0,并从 k 中减去 hash[i]
        • 如果 hash[i] 大于等于 k,将 i * k 累加到 ret 中,将 k 置为 0,并从 hash[i] 中减去 k,同时跳出循环。
      • 最后根据 k 的值和 hash 数组判断结果:
        • 如果 k 为 0 且 hash[3] + hash[2] + hash[1] 大于 0,说明可以完成任务,输出 ret + 1
        • 否则,输出 -1。
      • 释放哈希表的内存,防止内存泄漏。

关键细节

  • 哈希表的使用是为了方便存储和管理不同职业的士兵数量,避免使用复杂的数组存储方式。
  • 对 k - 1 个队伍的处理是为了逐步尝试能否满足组成 k 个纯职业小组的条件,根据不同余数情况分配士兵数量。
  • 在计算士兵数量和余数时,将士兵数量先减去 2 再处理余数,是为了后续更方便地计算所需的最少士兵数。
#include <stdio.h>
#include <stdlib.h>// 定义一个结构体作为哈希表的节点
typedef struct Node {int key;int value;struct Node* next;
} Node;// 创建一个新的节点
Node* createNode(int key, int value) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed\n");exit(1);}newNode->key = key;newNode->value = value;newNode->next = NULL;return newNode;
}// 向哈希表中插入元素
void insert(Node** hashTable, int size, int key, int value) {int index = abs(key) % size;Node* newNode = createNode(key, value);if (hashTable[index] == NULL) {hashTable[index] = newNode;} else {Node* temp = hashTable[index];while (temp->next!= NULL) {temp = temp->next;}temp->next = newNode;}
}// 在哈希表中查找元素
Node* find(Node** hashTable, int size, int key) {int index = abs(key) % size;Node* temp = hashTable[index];while (temp!= NULL) {if (temp->key == key) {return temp;}temp = temp->next;}return NULL;
}// 释放哈希表内存
void freeHashTable(Node** hashTable, int size) {for (int i = 0; i < size; ++i) {Node* temp = hashTable[i];while (temp!= NULL) {Node* toFree = temp;temp = temp->next;free(toFree);}}free(hashTable);
}#define HASH_SIZE 1000  // 哈希表的大小,可根据需要调整int main() {long long T, n, k;scanf("%lld", &T);while (T--) {scanf("%lld %lld", &n, &k);--k;Node** arr = (Node**)calloc(HASH_SIZE, sizeof(Node*));if (arr == NULL) {fprintf(stderr, "Memory allocation failed\n");exit(1);}int a, b;for (int i = 0; i < n; ++i) {scanf("%d %d", &a, &b);Node* node = find(arr, HASH_SIZE, a);if (node == NULL) {insert(arr, HASH_SIZE, a, b);} else {node->value += b;}}long long ret = 0;long long hash[4] = {0};for (int i = 0; i < HASH_SIZE; ++i) {Node* temp = arr[i];while (temp!= NULL) {int b = temp->value;if (b < 3) {ret += b;} else {ret += 2;b -= 2;hash[3] += b / 3;++hash[b % 3];}temp = temp->next;}}// k - 1 个队伍最多多少个人for (int i = 3; i > 0; --i) {if (hash[i] < k) {ret += i * hash[i];hash[i] = 0;k -= hash[i];} else {ret += i * k;k = 0;hash[i] -= k;break;}}if (k == 0 && hash[3] + hash[2] + hash[1] > 0) {printf("%lld\n", ret + 1);} else {printf("-1\n");}freeHashTable(arr, HASH_SIZE);}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com