logo标签列表

"在TopCoder中，FlowerGarden问题为什么是 DP 问题？"

algorithmdynamic-programming
6
我正在阅读Dumitru关于DP问题的优秀教程，链接在这里：http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static。我正在尝试为FlowerGarden问题提出基于DP的方法，该问题在1D DP问题列表中提到。
我只能想到一种非DP解决方案，它需要按照某些条件对花进行排序，然后根据问题中提到的不同条件重新排序它们。那不算是DP，对吧？
该编辑还没有提到任何关于DP的内容。是否有人可以指出一个正确的基于DP的解决方案呢？
谢谢！
编辑：
我没有意识到链接需要注册。这就是问题：
问题陈述 你要用球茎种植花园，以便在整个年份内享受到美丽的花朵。但是，您希望种植的花朵不会在可见时阻挡其他花朵。
您将得到一个int []高度，一个int [] bloom和一个int [] wilt。每种花卉由高度，bloom和wilt的相同索引处的元素表示。高度表示每种类型的花卉生长的高度，bloom表示每种类型的花卉从地面上冒出来的早晨，wilt表示每种类型的花卉枯萎并死亡的晚上。 bloom和wilt中的每个元素都将是介于1到365之间的数字，而wilt [i]将始终大于bloom [i]。您必须在单个行中种植所有相同类型的花卉以获得外观，并且您还希望尽可能向前种植最高的花卉。但是，如果一种花卉比另一种花卉更高，并且两种花卉可以同时不在地面上，则必须在较短的花卉前面种植较高的花卉以防止堵塞。花朵在早晨开放，在晚上凋零，因此即使在另一朵花凋零的同一天，一朵花也可以挡住另一朵花。
您应该返回一个int []，其中包含您应该按照上述目标种植的高度元素的顺序。花园的前部由返回值中的第一个元素表示，并且从那里查看花园。高度的元素将全部唯一，因此始终存在明确定义的顺序。
例1：
高度={5,4,3,2,1}
bloom={1,1,1,1,1}
wilt={365,365,365,365,365}
返回结果：

返回结果：{ 1, 2, 3, 4, 5 }

这些花都在一月一日盛开，十二月三十一日凋谢。由于它们可能会相互遮挡，因此您必须按高度从短到高排序。

例2：

h={5,4,3,2,1}

b={1,5,10,15,20}

w={4,9,14,19,24}

返回结果：{ 5, 4, 3, 2, 1 } 这组花现在都在不同时期盛开。由于它们永远不会相互遮挡，因此您可以按最高到最矮的顺序进行排序，以使最高的尽可能向前。

例3：

height={5,4,3,2,1}

bloom={1,5,10,15,20}

wilt={5,10,14,20,25}

返回结果：{ 3, 4, 5, 1, 2 } 这里的区别是第三种花比第四朵花的开放早一天凋谢。因此，我们可以先放置高度为3的花，然后是高度为4的花，然后是高度为5的花，最后是高度为1和2的花。请注意，我们也可以将它们按高度1排在首位，但是这不会导致园中最大的花放在第一位。

您的问题链接需要注册，请问您能否发布问题陈述？ - IVlad
1
请注意 http://forums.topcoder.com/ - Alexander
@Alexander - http://apps.topcoder.com/forums/?module=Thread&threadID=751778&start=0&mc=1#1560520 - GrowinMan
排序（height）。完成。我错过了什么？ - n. m.
@n.m.lol。看看这些例子，我刚刚添加了它们。我们希望更高的花朵靠近前面，但是如果在同一时刻有一朵高花和一朵矮花同时存在，我们希望矮花排在高花前面。 - GrowinMan
11个回答
4
这不是一个动态规划问题，而是一个贪心算法问题。
这也让我感到困惑，因为topcoder自己的动态规划教程将其链接为“初级”部分的练习题。
按高度排序花朵，从矮到高。从一个空行列表开始。对于每一朵花（从矮到高），找到最前面的位置，可以将该花插入其中，而不会阻挡后面的任何花。
在Python中：
def getOrdering(height, bloom, wilt):
    flowers = zip(height, bloom, wilt)
    flowers.sort()

    def flowersOverlap(f1, f2):
        # Overlap if each blooms before the other wilts.
        return f2[1] <= f1[2] and f1[1] <= f2[2]

    rows = [ ]
    for flower in flowers:
        rowIndex = len(rows)
        # Start at the back and march forward as long as
        # `flower` wouldn't block any flowers behind it.
        while rowIndex > 0 and not flowersOverlap(flower, rows[rowIndex - 1]):
            rowIndex -= 1
        rows[rowIndex:rowIndex] = [flower]

    return [flower[0] for flower in rows]
1
我也在这方面苦苦挣扎。如果我将花朵按照你所做的相反顺序（从大到小）排序，我们的目标就是这样。然后针对每朵花尝试找到可以合法放置的位置，例如，如果一朵名为A的花比另一朵较小的名为B的花的开放-凋零重叠时间更长，则将B往前移动。在示例中，大部分测试都通过了，但有些没有通过。我不明白这种方法存在问题在哪里。这种方法与你的方法非常相似，但它从最优顺序开始，然后尝试找到合法解决方案。 - David
2
public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
    int[] optimal = new int[height.length];
    int[] optimalBloom = new int[bloom.length];
    int[] optimalWilt = new int[wilt.length];

    // init state
    optimal[0] = height[0];
    optimalBloom[0] = bloom[0];
    optimalWilt[0] = wilt[0];

    // run dynamic programming
    for(int i = 1; i < height.length; i ++) {
        int currHeight = height[i];
        int currBloom = bloom[i];
        int currWilt = wilt[i];

        int offset = 0; // by default, type i is to be put to 1st row
        for(int j = 0; j < i; j ++) {
            if(currWilt >= optimalBloom[j] && currWilt <= optimalWilt[j] ||
                    currBloom >= optimalBloom[j] && currBloom <= optimalWilt[j] ||
                    currWilt >= optimalWilt[j] && currBloom <= optimalBloom[j]) {  // life period overlap
                if(currHeight < optimal[j]) {  // life overlap, and type i is shorter than type j
                    offset = j;
                    break;
                } else {
                    offset = j + 1; // type i overlap with type j, and i is taller than j. Put i after j
                }
            } else {  // not overlap with current
                if(currHeight < optimal[j]) {
                    offset = j + 1; // type i not overlap with j, i is shorter than j, put i after j
                }
                // else keep offset as is considering offset is smaller than j
            }
        }

        // shift the types after offset
        for(int k = i - 1; k >= offset; k -- ) {
            optimal[k+1] = optimal[k];
            optimalBloom[k+1] = optimalBloom[k];
            optimalWilt[k+1] = optimalWilt[k];
        }
        // update optimal
        optimal[offset] = currHeight;
        optimalBloom[offset] = currBloom;
        optimalWilt[offset] = currWilt;
    }
    return optimal;
}

这是我测试过的可行代码。

你的解决方案通过了https://community.topcoder.com/stat?c=problem_statement&pm=1918&rd=5006上提供的所有测试。您能详细说明一下，您的解决方案如何使用DP技术吗？我期望DP解决方案应该被定义为某个参数的逐步优化（最小化或最大化），使用一些DP公式来解决子问题的优化。例如，每个位置都会有一个Cost = Position-Height，并且每个元素的转置都会增加/降低解决方案的总成本。我们的目标是最大化花卉订购的最终成本。 - Slavik Derevianko
我认为我理解了你的解决方案如何使用DP。你的子问题在以下意义上是最优的：最初，你只取第一个元素（它的排序是最优的，因为它只有一个元素），然后添加下一个元素，并评估它们之间的最优排序（遵守像花卉寿命这样的条件）。每添加一朵花后，所有花都会重新排列以达到最佳顺序（根据条件），并在添加最后一朵花后（并重新排列所有花后），它们按最佳方式排序。做得好！ - Slavik Derevianko
这不就是插入排序和计数排序混合的另一种版本吗？ - daviddecoding
@SlavikDerevianko 对于中间重叠高度的情况失败。请查看我的答案https://dev59.com/GGXWa4cB1Zd3GeqPNoa2#42019806 - idelvall
1
我已经为此问题苦苦挣扎了整整一天，而且，我也找不到任何DP解决方案。
这是我的贪心方法（用Java实现），与其他已发布的方法类似，关键在于按高度顺序进行处理。原因是避免处理中间高度（指已计算的高度），因为一个中间高度可能会改变先前计算的相对顺序。
int[] height = new int[]{5, 3, 4};
int[] start =  new int[]{1, 3, 1};
int[] end =    new int[]{2, 4, 4};
System.out.println(Arrays.toString(new FlowerGarden().getOrdering(height, start, end)));

这是我能找到的唯一最优子结构。但是，考虑到子问题之间没有重叠，这个算法不应该被视为 DP，而应该被视为贪心算法。

private static boolean intersects(final int[] starts, final int[] ends, int i1, int i2) {
    return !(ends[i1] < starts[i2] || ends[i2] < starts[i1]);
}

public int[] getOrdering(final int[] height, final int[] starts, final int[] ends) {

    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        public int compare(Integer i, Integer j) {
            return Integer.compare(height[i], height[j]);
        }
    }
    );
    for (int i = 0; i < height.length; i++) {
        minHeap.add(i);
    }
    LinkedList<Integer> list = new LinkedList<Integer>();
    while (minHeap.size() > 0) {
        Integer index = minHeap.poll();
        int p = 1;
        int pos = 0;
        for (Integer i : list) {
            if (intersects(starts, ends, i, index)) {
                pos = p;
            }
            p++;
        }
        list.add(pos, index);
    }
    int[] ret = new int[height.length];
    int j = 0;
    for (Integer i : list) {
        ret[j++] = height[i];
    }
    return ret;
}

顺便说一下，我在这里看到的动态规划解决方案在这个例子中失败了。

干杯！

0

与Rob的代码相同，但使用Javascript（ES6）编写：

function getOrdering(height, bloom, wilt) {
    var n = height.length;

    var idx = [];
    for (var i = 0; i < n; ++i) idx[i] = i;

    idx.sort( (a, b) => height[a] - height[b] );

    var intersect = (a, b) => !(bloom[a] > wilt[b] || bloom[b] > wilt[a]);

    for (var i = 1; i < n; ++i) {
        // assume they are ordered correctly till index (i-1),
        // start moving flower i to the left until it can't move because of intersection
        var j = i, flw = idx[i];
        while (j > 0 && !intersect(idx[j-1], flw)) {
            idx[j] = idx[j-1];
            idx[--j] = flw;
        }
    }

    return idx.map( x => height[x] );
}
0

我已经用C++实现了这个程序。我使用了一个向量数据类型来分别存储高度、开花和凋落，然后按照高度对其进行排序，之后逐个取出花朵并根据与它们相关联的值进行排列。

以下是代码：

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

bool comp(pair<int, pair<int,int> >& a,pair<int, pair<int,int> >& b ){
    return (a.first > b.first);
}




bool justify(pair<int, pair<int,int> >& a,pair<int, pair<int,int> >& b, int k , int 
j,  vector<pair<int,pair<int,int> > >& v){
    if(((b.second.first <= a.second.first) && (b.second.second>= a.second.first)) || 
    ((b.second.first <= a.second.second) && (b.second.second>= a.second.second)) || 
    ((b.second.first > a.second.first) && (b.second.second < a.second.second) )){

            pair<int, pair<int,int> > temp = v[j];     
          int i = j-1;
       while(i >= k){

          v[i+1] = v[i];
          i--;


        }
        v[k] = temp;
        return true;
  }
  return false;
}




int main() {

  vector<pair<int,pair<int,int> > > v;
  int n,a,b,c;
  cin>>n;
  for(int i = 0;i < n;i++){
    cin>>a>>b>>c;
    v.push_back(make_pair(a,make_pair(b,c)));
 }


sort(v.begin(), v.end(), comp);



for(int j = 1;j < n;j++){
  for(int k = 0;k < j;k++){
    bool res = justify(v[k],v[j], k, j, v);
   if(res)
   break;
  }
 }

cout<<"output"<<endl;
for(int i = 0;i < n;i++){
    cout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<endl;
}
return 0;

}
0

与Rob类似，这是Python中稍微复杂的重叠的开花/凋谢检查。

H = 0
B = 1
W = 2

def getOrdering(heights, blooms, wilts):

    def _f1_after_f2(f1, f2):
        fs1 = set(range(f1[B], f1[W]+1))
        fs2 = set(range(f2[B], f2[W]+1))
        return f1[H] > f2[H] if fs2.intersection(fs1) != set([]) else False

    fs = zip(heights, blooms, wilts)
    fs.sort()
    ffs = []
    for f1 in fs:
        insert_at = len(ffs)
        for f2 in reversed(ffs):
            if _f1_after_f2(f1, f2): break
            insert_at -= 1
        ffs.insert(insert_at, f1)
    return [f[H] for f in ffs]
0
一个解决问题的图算法：
创建一个有向图(V,E)： V -> 花卉类型 E -> 两种花卉类型之间的关系
For all pairs (v_i, v_j)
  If v_i is smaller than v_j and v_j 'blocks' v_i
    draw an edge starting from v_i to v_j
For all nodes v_i
  Find the v_i with no incoming edges and the biggest height
   -> write it at the end of the result list
   -> remove v_i and all of its outgoing edges from graph

想要了解更多内容，请查阅以下论坛： Topcoder论坛-FlowerGarden

0

我的排序算法类似于插入排序。对于每一朵新的花，它从后往前遍历并检查前面的花是否会阻挡它；如果是，那么它必须放在它后面。同样地，它也从前往后搜索并检查后面的花是否会阻挡它；如果是，那么它必须放在它前面。如果没有阻碍，它就简单地检查高度最佳的位置。

#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");
}

/* Does A block B? */
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);

        /* front to back */
        int MinIdx = -1;
        for(int Idx = 0;
            Idx < FlowerIdx;
            ++Idx)
        {
            if(Blocks(Idx, FlowerIdx, Heights, Blooms, Wilts))
            {
                MinIdx = Idx;
                break;
            }
        }

        /* back to front */
        int MaxIdx = -1;
        for(int Idx = (FlowerIdx - 1);
            Idx >= 0;
            --Idx)
        {
            if(Blocks(FlowerIdx, Idx, Heights, Blooms, Wilts))
            {
                MaxIdx = (Idx + 1);
                break;
            }
        }

        /* best height index */
        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");
    }
}

编辑：这个解决方案非常糟糕，我想出了一个更好的动态规划解决方案。具体如下：对于每朵花，循环遍历所有其他花朵，检查它阻挡了哪些花朵；对于被它阻挡的那些花朵，再检查它们阻挡的所有花朵，以此类推，直到找到一朵不会阻挡任何其他花朵的花。将该花放入一个新数组中。回溯并将该花之前的每朵花放在该新数组的下一个位置。如果对每朵花都这样做，你将得到一个充满不阻挡其他花朵的花的数组。然后尽可能将每朵花向前放置。这个解决方案的动态规划部分是，有时你会遇到已经被另一朵花阻挡并已经放入新数组中的相同花朵，所以我们跳过该花朵而不是追踪它阻挡的花朵。

0
package topcoders;

import java.util.ArrayList;
import java.util.List;

public class FlowerGarden {

    public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
        int[] order = new int[height.length];
        List<Integer> heightList = new ArrayList<Integer>();
        for (int i = 0; i < height.length; i++) {
            heightList.add(height[i]);
        }
        heightList = quickSort(heightList);
        for (int i = 0; i < height.length; i++) {
            height[i] = heightList.get(i);
        }
        order = height;
        for (int i = 0; i < order.length; i++) {
            int j = 0;
            while (j < order.length - 1
                    && isBlocking(j + 1, j, order, bloom, wilt)) {
                int placeHolder = order[j];
                order[j] = order[j + 1];
                order[j + 1] = placeHolder;
                j++;
            }
        }

        return order;
    }

    public boolean isBlocking(int isBlocked, int isBlocking, int[] order,
            int[] bloom, int[] wilt) {
        if (order[isBlocking] > order[isBlocked]
                && bloom[isBlocked] <= wilt[isBlocking]
                && wilt[isBlocked] >= bloom[isBlocking]) {
            return true;
        } else {
            return false;
        }
    }

    public List<Integer> quickSort(List<Integer> array) {
        if (array.size() <= 1) {
            return array;
        }
        int pivotIndex = array.size() / 2;
        int pivot = array.get(pivotIndex);
        List<Integer> less = new ArrayList<Integer>();
        List<Integer> greater = new ArrayList<Integer>();
        int l = 0;
        int g = 0;
        for (int i = 0; i < array.size(); i++) {
            if (i == pivotIndex) {
                continue;
            } else if (array.get(i) >= pivot) {
                less.add(array.get(i));
            } else {
                greater.add(array.get(i));
            }
        }
        List<Integer> lessResult = quickSort(less);


        List<Integer> greaterResult = quickSort(greater);

        List<Integer> result = new ArrayList<Integer>();
        result.addAll(lessResult);
        result.add(pivot);
        result.addAll(greaterResult);



        return result;
    }

    public static void main(String[] args) {
        int[] height = { 5, 4, 3, 2, 1 };
        int[] bloom = { 1, 5, 10, 15, 20 };
        int[] wilt = { 5, 10, 14, 20, 25 };
        FlowerGarden g = new FlowerGarden();
        List<Integer> arrayList = new ArrayList<Integer>();
        int[] array = g.getOrdering(height, bloom, wilt);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}
0

我也尝试解决这个问题。我的方法的主要思路是构建一棵树，其中每个子节点至少被其父节点重叠一次。

例如，如果我们有三种高度分别为4、2和1的花在同一天生长和死亡，那么得到的树应该是：

All nodes overlap

另一方面，如果4和2和4和1同时存在，但2和1不共存，则生成的树应为：

Two brothers

这将生成一个符合问题约束的树。然而，问题陈述还包括成本函数，使得某些解决方案比其他解决方案更好。

...您还希望在更靠前的行中拥有尽可能高的花。

将此偏好投影到我们的树中的方法是将所有“兄弟”（共享相同父节点的所有节点）从高到低排序。因此，2先于1。

我使用以下代码构建了这棵树：

#define INT_MOD(a,b) ((a<0)?(b+(a%b)):(a%b))
#define DIST(a,b) ((a-b>=0)?(a-b):(b-a))

//Prev: ForAll(i), bloom[i] < wilt[i]
inline bool isOverlap(vector<int> & bloom,
                      vector<int> & wilt,
                      vector<int> & height,
                      unsigned int idxPrev, unsigned int idxFollowing)
{
    int f1A = bloom[idxPrev];
    int f1B = wilt[idxPrev];
    int f2A = bloom[idxFollowing];
    int f2B = wilt[idxFollowing];

    bool notIntersecting = 
    f2A > f1B /* --[--]-(--)-- */ ||
    f1A > f2B /* --(--)-[--]-- */ ;

    return height[idxPrev] > height[idxFollowing] && !notIntersecting;
}


class CPreference {
public:
    static vector<int> * pHeight;
    static bool preference(int a, int b)
    {
        return (*pHeight)[a] > (*pHeight)[b];
    }
};
vector<int> * CPreference::pHeight = NULL;

vector<int> getOrdering(vector<int> height,
                        vector<int> bloom,
                        vector<int>  wilt)
{
    int l = height.size();
    vector<int> state = vector<int>(l, -1); /*  Tree where each leave points to its
                                                parent. Being that parent the first
                                                flower type that is forced to be
                                                after (backwards) its children */

    //This loop is the dynamic programming core.
    for(int i = 0; i < l; i++)
        for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
        {
            if(isOverlap(bloom, wilt, height, i, j) &&
                (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
            {
                state[j] = i;
            }
        }

    vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
    for(int i = 0; i < l+1; i++)
        groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

    for(int i = 0; i < l; i++)
    {
        int k = state[i];
  if(k < 0) k = l;
  groups[k].push_back(i);
}

CPreference::pHeight = &height;
for(vector<vector<int> >::iterator it = groups.begin(); it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

此时，groups 的每一行（i）都包含按从高到低的顺序排列的所有花卉类型索引，这些索引应该放在索引 i 的花卉类型之前。

还需要进行最后一步操作，将groups展平为输出向量。也就是说，构建一个向量，其中每个元素后面要么是：

  • 它在树上的父节点。
  • 按高度排序后的下一个兄弟。

可以通过对group的每个节点进行深度访问来完成。我认为这是我的解决方案的薄弱点。由于时间不够，所以我只做了一个天真的递归实现：

//PRE: each vector, v, in 'groups' is sorted using CPreference
void flattenTree(vector<vector<int> > & groups, vector<int> & out, int currentIdx /*parent*/, int l)
{
    int pIdx = currentIdx;
    if(pIdx < 0) pIdx = l;

    vector<int> & elements = groups[pIdx];
    vector<int> ret;

    for(vector<int>::iterator it = elements.begin(); it != elements.end(); it++)
    {
        flattenTree(groups, out ,*it, l);
    }

    if(currentIdx>=0)
        out.push_back(currentIdx);
}

用于完成getOrdering函数的是什么：

vector<int> getOrdering(vector<int> height,
            vector<int> bloom,
            vector<int>  wilt)
{
  int l = height.size();
  vector<int> state = vector<int>(l, -1); /* Tree where each leave points to its
                         parent. Being that parent the first
                         flower type that is forced to be
                         after (backwards) its children */
  for(int i = 0; i < l; i++)
    for(int j = INT_MOD((i-1),l); j != i; j = INT_MOD((j-1),l))
      {
        if(isOverlap(bloom, wilt, height, i, j) &&
        (state[j] < 0 || DIST(height[j],height[i]) < DIST(height[j], height[state[j]])))
        {
            state[j] = i;
        }
      }

  vector<vector<int> > groups; //Groups of indexes overlapped by the element at the same index
  for(int i = 0; i < l+1; i++)
    groups.push_back(vector<int>()); // (l+1) for no overlapped indexes group.

  for(int i = 0; i < l; i++)
    {
      int k = state[i];
      if(k < 0) k = l;
      groups[k].push_back(i);
    }

  CPreference::pHeight = &height;
  for(vector<vector<int> >::iterator it = groups.begin();
      it != groups.end(); it++)
    sort(it->begin(),it->end(), CPreference::preference);

   vector<int> ret;
   flattenTree(groups, ret, -1, l);
   for(unsigned int i = 0; i < ret.size(); i++)
    ret[i] = height[ret[i]];
    return ret; 
}

请告诉我，如果您找到了更好的解决方案或者知道任何改进我的方法的方式，请告诉我。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接