伙计们我有一个项目，在其中给了我很多椅子，许多阳伞以及椅子的位置。我认为必须找到所有遮阳伞的最佳宽度（彼此相等）以覆盖每把椅子。我精心编写了以下代码，使其适用于赋值文件中的示例案例（虽然很杂乱，但是可以）：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
void search();
int* constructParasols();
int check();
void draw();
int main(void)
{
int n, k, totalSize;
scanf("%d", &n);
printf("\n");
scanf("%d", &k);
printf("\n");
int* chairs = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < n; i++)
{
scanf("%d", &chairs[i]);
}
printf("\n");
totalSize = chairs[n - 1];
search(n, k, chairs, totalSize, 0, totalSize/k);
free(chairs);
chairs = NULL;
system("pause");
}
void search(int n, int k, int* chairs, int totalSize, int low, int hi)
{
int mid = (low + hi)/2;
int tempPos = 0;
if (low >= hi - 1)
{
if (check(n, k, low, chairs, constructParasols(k,totalSize,low), k - 2, totalSize - (low * 2), totalSize) == 1)
{
printf("width %d is optimal\n", low);
}
else if (check(n, k, hi, chairs, constructParasols(k, totalSize, hi), k - 2, totalSize - (low * 2), totalSize) == 1)
{
printf("width%d is optimal\n", hi);
}
else
{
printf("no solution found\n");
}
}
else if (check(n, k, mid, chairs, constructParasols(k, totalSize, mid), k - 2, totalSize - (mid * 2), totalSize) == 1)
{
search(n, k, chairs, totalSize, low, mid-1);
}
else
{
search(n, k, chairs, totalSize, mid+1, hi);
}
}
int* constructParasols(int k, int totalSize, int width)
{
int* parasols = (int*)calloc(k + 1, sizeof(int));
int tempPos = 0;
for (int i = 0; i < k - 1; i++)
{
parasols[i] = tempPos;
tempPos += width;
}
parasols[k - 1] = totalSize - width;
return parasols;
}
int check(int n, int k, int width, int* chairs, int* parasols, int pNum, int maxPos, int totalSize)
{
int* cover = (int*)calloc(totalSize + 1, sizeof(int));
int failed = 0;
for (int i = 0; i < totalSize; i++)
{
cover[i] = 0;
}
if (k<=2)
{
draw(n, k, width, chairs, parasols, totalSize);
for (int i = 0; i < width; i++)
{
cover[i] = 1;
if(k==2) cover[parasols[1] + i] = 1;
}
for (int i = 0; i < n; i++)
{
if (cover[chairs[i] - 1] == 0)
{
failed = 1;
}
}
if (failed == 0)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 1;
}
else
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 0;
}
}
draw(n, k, width, chairs, parasols, totalSize);
for (int i = 0; i < k; i++)
{
for (int j = 0; j < width; j++)
{
cover[parasols[i] + j] = 1;
}
}
for (int i = 0; i < n; i++)
{
if (cover[chairs[i]-1] == 0)
{
failed = 1;
}
}
if (failed == 0)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 1;
}
if (pNum <= 1 && parasols[pNum] == maxPos)
{
free(cover);
cover = NULL;
free(parasols);
parasols = NULL;
return 0;
}
else if (parasols[pNum] == maxPos)
{
free(cover);
cover = NULL;
return check(n, k, width, chairs, parasols, pNum - 1, maxPos - width, totalSize);
}
else
{
free(cover);
cover = NULL;
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
}
void draw(int n, int k, int width, int* chairs, int* parasols, int totalSize)
{
int* dCover = (int*)calloc(totalSize, sizeof(int));
int* chairPos = (int*)calloc(totalSize, sizeof(int));
for (int i = 0; i < totalSize; i++)
{
dCover[i] = 0;
chairPos[i] = 0;
}
for (int i = 0; i < k; i++)
{
for (int j = 0; j < width; j++)
{
if (dCover[parasols[i] + j] >= 1) dCover[parasols[i] + j] = 2;
else dCover[parasols[i] + j] = 1;
}
}
for (int i = 0; i < n; i++)
{
chairPos[chairs[i]-1] = 1;
}
for (int i = 0; i <= totalSize; i++)
{
if (dCover[i] == 2)
{
printf("=");
}
else if (dCover[i] == 1)
{
printf("-");
}
else
{
printf(" ");
}
}
printf("\n");
for (int i = 0; i <= totalSize; i++)
{
if (chairPos[i] == 1)
{
printf("|");
}
else
{
printf(" ");
}
}
printf("\n");
free(dCover);
dCover = NULL;
free(chairPos);
chairPos = NULL;
return;
}
（为了清晰和减小了尺寸，删除了一些注释和调试打印）
但是，这些只是他将尝试的十个样本中的两个样本。我想让它们都正确无误，因为我是编程方面的完美主义者，并且在检查封面是否有效的过程中发现了一个盲点。现在，它将从右边拿起第二把阳伞，将它逐个空间拖移并每次检查。一旦它接触到它右边的阳伞，它将从左边的下一个阳伞开始，并执行此操作直到剩下最左边的阳伞，并得出此配置不会成功的结论。
这意味着，如果我输入示例输入，例如8 4 1 3 6 9 12 15 17 20，
无法检查阳伞宽度为4且均匀隔开的情况。我着手通过更改以下内容来纠正此问题：
else
{
free(cover);
cover = NULL;
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
（这是它尝试将阳伞向左推，然后再试一次）的位置：
else
{
printf("freeing cover\n");
free(cover);
cover = NULL;
printf("iteration failed\n");
//parasols[pNum]++;
//return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
if (parasols[pNum] != parasols[pNum - 1] + width && check(n, k, width, chairs, parasols, pNum - 1, parasols[pNum]-width, totalSize) == 1)
{
return 1;
}
else
{
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
}
似乎很有意义。仅当我现在运行它时，我才会遇到读取访问冲突。就在这儿：
else dCover[parasols[i] + j] = 1;
dCover。在draw命令下。
它会抓住遮阳伞并将其移至右侧，检查它，然后抓住遮阳伞至其左侧并将其移至右侧。正如我所期望的。只有在
引发异常的地方。
如果我还原代码，则一切正常。我不知道这和它有什么关系-完全是两个不同的指针。我正在使用Visual Studio 2017来构建它，如果有区别的话。有人可以帮我吗？
最佳答案
当释放已经释放的指针时，您会遇到这种迷恋。
您可以释放parasols中的check，并继续使用它而无需重建它。
在代码的这一部分中：
if (parasols[pNum] != parasols[pNum - 1] + width && check(n, k, width, chairs, parasols, pNum - 1, parasols[pNum]-width, totalSize) == 1)
{
return 1;
}
else
{
parasols[pNum]++;
return check(n, k, width, chairs, parasols, pNum, maxPos, totalSize);
}
check失败了，返回了0，所以您进入free(parasols)，并再次在else和parasols[pNum]++中使用了它，而没有重构return check(...。程序在第二个
parasols中崩溃，但是在访问释放的指针时也可能崩溃。