我的排序算法类似于插入排序。对于每一朵新的花,它从后往前遍历并检查前面的花是否会阻挡它;如果是,那么它必须放在它后面。同样地,它也从前往后搜索并检查后面的花是否会阻挡它;如果是,那么它必须放在它前面。如果没有阻碍,它就简单地检查高度最佳的位置。
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#define uint32 uint32_t
static void
Swap(int *AIdx, int *BIdx)
{
int Tmp = *AIdx;
*AIdx = *BIdx;
*BIdx = Tmp;
}
static void
SwapTo(int Start, int End, int *Array)
{
while(Start != End)
{
Swap(&Array[Start], &Array[Start - 1]);
--Start;
}
}
static void
PrintTo(int End, int *Array)
{
for(int Idx = 0;
Idx < End;
++Idx)
{
printf("%d, ", Array[Idx]);
}
printf("\n");
}
static bool
Blocks(int AIdx, int BIdx, int *Heights, int *Blooms, int *Wilts)
{
bool Result = (Heights[AIdx] > Heights[BIdx] &&
Wilts[AIdx] >= Blooms[BIdx] &&
Blooms[AIdx] <= Wilts[BIdx]);
return Result;
}
static void
Order(int *Heights, int *Blooms, int *Wilts,
int FlowerCount)
{
for(int FlowerIdx = 1;
FlowerIdx < FlowerCount;
++FlowerIdx)
{
PrintTo(FlowerIdx, Heights);
int MinIdx = -1;
for(int Idx = 0;
Idx < FlowerIdx;
++Idx)
{
if(Blocks(Idx, FlowerIdx, Heights, Blooms, Wilts))
{
MinIdx = Idx;
break;
}
}
int MaxIdx = -1;
for(int Idx = (FlowerIdx - 1);
Idx >= 0;
--Idx)
{
if(Blocks(FlowerIdx, Idx, Heights, Blooms, Wilts))
{
MaxIdx = (Idx + 1);
break;
}
}
int BestHeightIdx = -1;
if(MinIdx == -1 &&
MaxIdx == -1)
{
for(int Idx = 0;
Idx < FlowerIdx;
++Idx)
{
if(Heights[FlowerIdx] > Heights[Idx])
{
BestHeightIdx = Idx;
break;
}
}
if(BestHeightIdx == -1)
{
BestHeightIdx = FlowerIdx;
}
}
int SwapToIdx = -1;
if((MaxIdx == -1 && MinIdx != -1) ||
(MinIdx == -1 && MaxIdx != -1) ||
(MaxIdx != -1 && MinIdx != -1 && MaxIdx == MinIdx))
{
SwapToIdx = (MinIdx != -1) ? MinIdx : MaxIdx;
}
else if(BestHeightIdx != -1)
{
SwapToIdx = BestHeightIdx;
}
else
{
fprintf(stderr, "Spot-finding error:\n MinIdx: %d, MaxIdx: %d, BestHIdx: %d\n",
MinIdx, MaxIdx, BestHeightIdx);
exit(1);
}
SwapTo(FlowerIdx, SwapToIdx, Heights);
SwapTo(FlowerIdx, SwapToIdx, Blooms);
SwapTo(FlowerIdx, SwapToIdx, Wilts);
}
}
int
main(int argc, char *argv[])
{
int Heights0[] = {5,4,3,2,1};
int Blooms0[] = {1,1,1,1,1};
int Wilts0[] = {365,365,365,365,365};
int Heights1[] = {5,4,3,2,1};
int Blooms1[] = {1,5,10,15,20};
int Wilts1[] = {4,9,14,19,24};
int Heights2[] = {5,4,3,2,1};
int Blooms2[] = {1,5,10,15,20};
int Wilts2[] = {5,10,15,20,25};
int Heights3[] = {5,4,3,2,1};
int Blooms3[] = {1,5,10,15,20};
int Wilts3[] = {5,10,14,20,25};
int Heights4[] = {1,2,3,4,5,6};
int Blooms4[] = {1,3,1,3,1,3};
int Wilts4[] = {2,4,2,4,2,4};
int Heights5[] = {3,2,5,4};
int Blooms5[] = {1,2,11,10};
int Wilts5[] = {4,3,12,13};
int *AllHeights[] = {Heights0, Heights1, Heights2, Heights3, Heights4, Heights5};
int *AllBlooms[] = {Blooms0, Blooms1, Blooms2, Blooms3, Blooms4, Blooms5};
int *AllWilts[] = {Wilts0, Wilts1, Wilts2, Wilts3, Wilts4, Wilts5};
int AllFlowerCounts[] = {5, 5, 5, 5, 6, 4};
printf("\n");
for(int Idx = 0;
Idx < 6;
++Idx)
{
int *Heights = AllHeights[Idx];
int *Blooms = AllBlooms[Idx];
int *Wilts = AllWilts[Idx];
int FlowerCount = AllFlowerCounts[Idx];
printf("Test %d\n", Idx);
Order(Heights, Blooms, Wilts, FlowerCount);
printf("{ ");
for(int Idx = 0;
Idx < FlowerCount;
++Idx)
{
printf("%d", Heights[Idx]);
if(Idx != (FlowerCount - 1))
{
printf(", ");
}
}
printf(" }\n\n");
}
}
编辑:这个解决方案非常糟糕,我想出了一个更好的动态规划解决方案。具体如下:对于每朵花,循环遍历所有其他花朵,检查它阻挡了哪些花朵;对于被它阻挡的那些花朵,再检查它们阻挡的所有花朵,以此类推,直到找到一朵不会阻挡任何其他花朵的花。将该花放入一个新数组中。回溯并将该花之前的每朵花放在该新数组的下一个位置。如果对每朵花都这样做,你将得到一个充满不阻挡其他花朵的花的数组。然后尽可能将每朵花向前放置。这个解决方案的动态规划部分是,有时你会遇到已经被另一朵花阻挡并已经放入新数组中的相同花朵,所以我们跳过该花朵而不是追踪它阻挡的花朵。