C语言 在仓库之间移动箱子:内存分配问题

zbdgwd5y  于 2024-01-06  发布在  其他
关注(0)|答案(1)|浏览(96)

任务

M个仓库(M <= 100000),里面有一定重量的货物。首先,我们有M行输入,每行看起来像这样:
t a1 a2 a3 a4.
其中t为仓库内已排列的物品数量,a1 a2 a3 a4.为重量(t <= 1000000000000000,重量<= 214747483647)
然后,我们得到两种类型的Q查询(Q <= 200000):

K-打印出每个仓库内所有货物的总重量
Rmz md tp tk -将索引在tptk之间(含)的所有器皿从索引号为mz的仓库移动到索引为md的仓库端。

mz,md <= 100000
-255 <= tp,tk <= 255

索引从1开始(索引1 -第一个项目,索引2 -第二个项目,等等)。负索引-n意味着我想要一个索引为n的项目从末尾开始计数(因此-1将是仓库中的最后一个项目)。

基本上,如果我有两个仓库的项目(他们的重量)安排这样,

**1.**2 3 4
**2.**5 12 1

然后我输入:
R 2 1 1 -1
K
我将把所有物品从仓库2移到仓库1的末尾(保持它们的顺序),这样看起来就像这样:

**1.**2 3 4 5 12 1
2.

然后像这样打印出两者的和:
27 0

示例
AInput:

1 1
1 1
K
输出量:
1

B输入:

3 5
2 1 1
0
4 1 2 3 4
K
R 3 2 1 - 1
K
R 2 1 1 1
K
输出量:
2 0 10
2 10 0
3 9 0

CInput:

2 6
3 2 2 2
2 3 3
K
R 1 2 2 - 2
K
R 1 2 1 - 1
R 2 1 1 -1
K
输出量:
6 6
4 8
12 0

我的密码

我已经写了一些基本的基础,我希望完成的程序看起来像:

  1. #include <stdio.h>
  2. int main() {
  3. long int M,Q,t,ware;
  4. if (scanf("%ld %ld",&M,&Q) != 2)
  5. {
  6. printf("Invalid Input");
  7. }
  8. char check;
  9. //declaration of warehouse size - subject to change
  10. long int warehouses[M+1][1000];
  11. //array with sums of weights of items in each warehouse
  12. long long int sumy[M+1];
  13. //array with sizes of each warehouse
  14. long int length[M+1];
  15. for (int i = 1; i<M+1;i++)
  16. {
  17. if (scanf(" %ld",&t) != 1)
  18. {
  19. printf("Invalid Input");
  20. }
  21. length[i] = t;
  22. for (int j = 1; j<t+1;j++)
  23. {
  24. if (scanf(" %ld",&ware) != 1)
  25. {
  26. printf("Invalid Input");
  27. }
  28. warehouses[i][j] = ware;
  29. sumy[i] += ware;
  30. }
  31. }
  32. long int mz,md;
  33. int tp,tk;
  34. for (int k = 0;k<Q;k++)
  35. {
  36. if (scanf(" %c",&check) != 1)
  37. {
  38. printf("Invalid Input");
  39. }
  40. if (check == 'K')
  41. {
  42. for (int ki = 0; ki < M;ki++)
  43. {
  44. printf("%lld",sumy[ki+1]);
  45. printf(" ");
  46. }
  47. printf("\n");
  48. }else
  49. {
  50. //indexes of "from warehouse" and "to warehouse"
  51. if (scanf(" %ld %ld",&mz,&md) != 2)
  52. {
  53. printf("Invalid Input");
  54. }
  55. //indexes of the range of items we want to transport
  56. if (scanf(" %d %d",&tp,&tk) != 2)
  57. {
  58. printf("Invalid Input");
  59. }
  60. if (tp < 0)
  61. {
  62. tp = length[mz] + tp + 1;
  63. }
  64. if (tk < 0)
  65. {
  66. tk = length[mz] + tk + 1;
  67. }
  68. for (int kj = 0; kj <= tk - tp ;kj++)
  69. {
  70. //moving items - subject to change
  71. warehouses[md][length[md]+1] = warehouses[mz][tp + kj];
  72. sumy[mz] -= warehouses[mz][tp + kj];
  73. sumy[md] += warehouses[mz][tp + kj];
  74. warehouses[mz][tp + kj] = 0;
  75. length[md] += 1;
  76. length[mz] -= 1;
  77. }
  78. }
  79. }
  80. return 0;
  81. }

字符串
一个明显的问题是像这样声明2D数组long int warehouses[M+1][1000];(低效的内存管理+我不能让它像它应该的那样大,因为它需要太多的内存)而不是动态地做,但这正是我做这个线程的原因。我对C编程有点陌生,使用内存分配和指针对我来说仍然很困难。理想情况下,我希望这段代码有一个“动态2D数组”(使用指针数组,但也许有人有更好的主意),然后根据货物的运输重新分配大小。如果有人可以重写这些部分,并帮助我了解他们是如何工作的,我会非常感激。建议也欢迎。

kq4fsx7k

kq4fsx7k1#

使用链接列表调整:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct Node {
  4. int weight;
  5. struct Node *next;
  6. } Node;
  7. typedef struct {
  8. Node *head;
  9. Node *tail;
  10. } Warehouse;
  11. Warehouse warehouses[100001];
  12. void insertItem(int mz, int weight) {
  13. Node *newNode = (Node *)malloc(sizeof(Node));
  14. newNode->weight = weight;
  15. newNode->next = NULL;
  16. if (warehouses[mz].head == NULL) {
  17. warehouses[mz].head = warehouses[mz].tail = newNode;
  18. } else {
  19. warehouses[mz].tail->next = newNode;
  20. warehouses[mz].tail = newNode;
  21. }
  22. }
  23. void adjustNegativeIndex(int mz, int *tp, int *tk, int length[]) {
  24. if (*tp < 0) {
  25. *tp = length[mz] + *tp + 1;
  26. }
  27. if (*tk < 0) {
  28. *tk = length[mz] + *tk + 1;
  29. }
  30. }
  31. void moveItems(int mz, int md, int tp, int tk) {
  32. Node *start = warehouses[mz].head;
  33. Node *prev = NULL;
  34. int count = 1;
  35. while (count < tp && start != NULL) {
  36. prev = start;
  37. start = start->next;
  38. count++;
  39. }
  40. Node *end = start;
  41. count = tp;
  42. while (count < tk && end != NULL) {
  43. end = end->next;
  44. count++;
  45. }
  46. if (start == NULL || end == NULL) return;
  47. if (prev == NULL) {
  48. warehouses[mz].head = end->next;
  49. } else {
  50. prev->next = end->next;
  51. }
  52. if (warehouses[md].head == NULL) {
  53. warehouses[md].head = start;
  54. } else {
  55. warehouses[md].tail->next = start;
  56. }
  57. warehouses[md].tail = end;
  58. end->next = NULL;
  59. }
  60. void printTotalWeights(int m) {
  61. for (int i = 1; i <= m; i++) {
  62. int sum = 0;
  63. Node *curr = warehouses[i].head;
  64. while (curr != NULL) {
  65. sum += curr->weight;
  66. curr = curr->next;
  67. }
  68. printf("%d ", sum);
  69. }
  70. printf("\n");
  71. }
  72. int main() {
  73. int m, q;
  74. if (scanf("%d %d", &m,&q) != 2)
  75. {
  76. printf("Invalid Input");
  77. return 0;
  78. }
  79. int length[m+1];
  80. for (int i = 1; i <= m; i++) {
  81. int t, weight;
  82. if (scanf(" %d", &t) != 1)
  83. {
  84. printf("Invalid Input");
  85. return 0;
  86. }
  87. length[i] = t;
  88. for (int j = 0; j < t; j++) {
  89. if (scanf(" %d", &weight) != 1)
  90. {
  91. printf("Invalid Input");
  92. return 0;
  93. }
  94. insertItem(i, weight);
  95. }
  96. }
  97. while (q--) {
  98. char op;
  99. if (scanf(" %c", &op) != 1) {
  100. printf("Invalid Input");
  101. return 0;
  102. }
  103. if (op == 'K') {
  104. printTotalWeights(m);
  105. } else {
  106. int mz, md, tp, tk;
  107. if (scanf("%d %d %d %d", &mz, &md, &tp, &tk) != 4) {
  108. printf("Invalid Input");
  109. return 0;
  110. }
  111. adjustNegativeIndex(mz, &tp, &tk, length);
  112. moveItems(mz, md, tp, tk);
  113. length[mz] -= tk-tp+1;
  114. length[md] += tk-tp+1;
  115. }
  116. }
  117. return 0;
  118. }

字符串

展开查看全部

相关问题