Sie sollten ein Programm oder eine Funktion schreiben, die eine nicht negative Ganzzahl kund eine sortierte Ganzzahlliste Lals Ein- und Ausgabe verwendet oder eine geglättete Liste zurückgibt M.

Mwird aus der aufsteigenden Liste erstellt, Lindem höchstens kganzzahlige Elemente eingefügt werden, während die Liste sortiert bleibt . Die eingefügten Ganzzahlen sollten so gewählt werden, dass die maximale Vorwärtsdifferenz von Mso gering wie möglich ist. Wir werden diesen kleinsten Wert "Glätte" nennen.

Die Vorwärtsdifferenzen der Liste -1 3 8 11 15sind 4 5 3 4und die maximale Vorwärtsdifferenz ist 5.

Mit 2Einfügungen die Glätte 2 10 15heißt 4und eine mögliche Ausgabe ist 2 6 10 11 15mit Vorwärtsdifferenzen 4 4 1 4.

Eingang

• Eine nicht negative ganze Zahl k.
• Eine aufsteigende Ganzzahlliste Lmit mindestens 2 Elementen.

Ausgabe

• Die aufsteigende Ganzzahlliste M.
• Wenn mehrere richtige Antworten vorhanden sind, geben Sie genau eine davon aus (eine davon ist ausreichend).
• Ihre Lösung muss jeden Beispieltestfall auf meinem Computer in weniger als einer Minute lösen (ich teste nur enge Fälle. Ich habe einen unterdurchschnittlichen PC.).

Beispiele

Eingabe ( k, L) => Eine mögliche Ausgabe und die maximale Vorwärtsdifferenz (die nicht Teil der Ausgabe ist) in Klammern

0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)

Dies ist Code-Golf, also gewinnt der kürzeste Einstieg.

Pyth, 28 27 Bytes

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Eingabe wie folgt:

3
[2, 10, 15]

Demonstration. Kabelbaum testen.

Hinweis: Als die Frage gestellt wurde, gab es in Pyth einen kleinen Fehler in Bezug auf die Verwendung von rFdinside u, den ich gerade behoben habe. Der Fehler machte es unmöglich, jemals Fdrinnen zu verwenden u, was definitiv nicht beabsichtigt war.

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

                               Implicit:
                               z is the number of insertions, in string form.
                               Q is the input list.
              C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
           rFd                 d = (a, b) -> range(a, b)
        %hH                    Take every H+1th element of that range
       t                       And throw out the first one.
      m                        Perform this process for each element pair
     s                         And combine the results into one list.

                               The above is a minimal set of additional elements
                               To reduce the maximal difference to H+1.

  u                     hvz    Repeat until the result stops changing, where
                               the prior result is G, H starts at 0 and
                               increases by 1 each repetition, and
                               G is initialized to eval(z)+1.
   ?               >GvzG       If not G[eval(z):], return G. In other words,
                               if the prior result was short enough, stop.
                               Also, this is always false on the initial call.
    smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.

Hier ist eine Version, die zum Zeitpunkt der Beantwortung der Frage mit dem Dolmetscher zusammengearbeitet hätte. Es ist 28 Byte groß und funktioniert genauso:

S+Qu?smt%hHr.udC,QtQ>GvzGhvz

Demonstration.

Git-Commit der entsprechenden Version, f6b40e62

Python 2, 104

def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)

Versucht verschiedene maximale Inkremente d, beginnend mit 1 bis zum Aufwärtszählen. Füllt Lücken für jedes Paar (p,x)aufeinanderfolgender Elemente aus, indem jede dNummer in der Lücke genommen wird. Wenn Mdas Kontingent überschritten wird, versuchen Sie es erneut mit einem höheren Kontingent d. Andernfalls wird eine Liste der hinzugefügten und ursprünglichen Elemente sortiert zurückgegeben.

Dies erledigt alle Testfälle ohne Verzögerung auf meinem Rechner.