本帖最后由 yuxijian2020 于 2021-5-12 23:33 编辑
工具人报到
太晚了,就弄了第一个#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//从 pos 开始往左 找到第一个 0值 在数组中的位置距离当前位置的距离
int LeftFindZero(int* box, int num, int pos)
{
int cur = (pos - 1) < 0 ? num - 1 : pos - 1;
int distance = 1;
while (box[cur] != 0)
{
distance++;
cur = (cur - 1) < 0 ? num - 1 : cur - 1;
}
return distance;
}
//从 pos 开始往右 找到第一个 0值 在数组中的位置距离当前位置的距离
int RightFindZero(int* box, int num, int pos)
{
int cur = (pos + 1) < num ? pos + 1 : 0;
int distance = 1;
while (box[cur] != 0)
{
distance++;
cur = (cur + 1) < num ? cur + 1 : 0;
}
return distance;
}
//优先向左边填充
int LeftFindNearestZeroAndSwap(int* box, int num, int pos)
{
int leftZero = LeftFindZero(box, num, pos);
int rightZero = RightFindZero(box, num, pos);
int cur = 0;
if (leftZero > rightZero)
{
cur = rightZero + pos >= num ? (rightZero + pos - num) : rightZero + pos;
box[cur]++;
box[pos]--;
return rightZero;
}
else
{
cur = pos - leftZero < 0 ? (pos + num - leftZero) : pos - leftZero;
box[cur]++;
box[pos]--;
return leftZero;
}
}
//优先向右边填充
int RightFindNearestZeroAndSwap(int* box, int num, int pos)
{
int leftZero = LeftFindZero(box, num, pos);
int rightZero = RightFindZero(box, num, pos);
int cur = 0;
if (rightZero > leftZero)
{
cur = pos - leftZero < 0 ? (pos + num - leftZero) : pos - leftZero;
box[cur]++;
box[pos]--;
return leftZero;
}
else
{
cur = rightZero + pos >= num ? (rightZero + pos - num) : rightZero + pos;
box[cur]++;
box[pos]--;
return rightZero;
}
}
//分发
int HandOut(int* box, int num)
{
if (num <= 0) return 0;
int left = 0; //左边
int right = 0; //右边
int leftCount = 0; //优先往左移动
int rightCount = 0; //优先往右移动
int count = 0; //返回值
int* leftBox = (int*)malloc(sizeof(int) * num); //临时数组
int* rightBox = (int*)malloc(sizeof(int) * num); //临时数组
if (leftBox == NULL || rightBox == NULL) return 0;
memset(leftBox, 0, sizeof(int) * num);
memset(rightBox, 0, sizeof(int) * num);
for (int i = 0; i < num; i++)
{
leftBox[i] = box[i];
rightBox[i] = box[i];
}
for (int i = 0; i < num; i++)
{
while (leftBox[i] > 1)
leftCount += LeftFindNearestZeroAndSwap(leftBox, num, i);
}
for (int j = num - 1; j >= 0; j--)
{
while (rightBox[j] > 1)
rightCount += RightFindNearestZeroAndSwap(rightBox, num, j);
}
free(leftBox);
free(rightBox);
count = leftCount > rightCount ? rightCount : leftCount;
return count;
}
void OperatorCount()
{
int t = 51; //数据组数
int N = 501; //盒子数量 和 糖果的最大数量
int** boxs; //盒子
int* result; //结果
//获取用户输入
while (t < 0 || t > 50)
{
printf_s("本次输入几组数据?(0 <= t <= 50)\n");
scanf_s("%d%*c", &t);
if (t < 0 || t > 50)
printf_s("输入错误,请重新输入 t\n");
}
while (N < 1 || N > 500)
{
printf_s("共有几个盒子?(1 <= N <= 500)\n");
scanf_s("%d%*c", &N);
if (N < 1 || N > 500)
printf_s("盒子数量错误!请重新输入!\n");
}
//申请空间
boxs = (int**)malloc(sizeof(int*) * t);
if (boxs == NULL) return; //判断是否申请成功
for (int i = 0; i < t; i++)
{
boxs[i] = (int*)malloc(sizeof(int) * N);
if (boxs[i] == NULL) return;
memset(boxs[i], 0, sizeof(int) * N);
}
result = (int*)malloc(sizeof(int) * t);
if (result == NULL) return;
memset(result, 0, sizeof(int) * t);
for (int i = 0; i < t; i++)
{
for (int j = 0; j < N; j++)
{
printf_s("请输入第 %d 组 第 %d 个盒子中的糖果数量:", i, j);
scanf_s("%d", &boxs[i][j]);
}
result[i] = HandOut(boxs[i], N);
}
for (int i = 0; i < t; i++)
printf_s("第 %d 组数据需要至少操作 %d 次\n", i, result[i]);
free(result);
for (int i = 0; i < t; i++)
free(boxs[i]);
free(boxs);
}
int main()
{
OperatorCount();
system("pause");
return 0;
}
|