INVCNT上的NZEC与Spoj上的欺骗

Question

我使用下面的NZEC代码获得INVCNT

; for lists of length > 2 inversions are the same as the number of elements
; against which the first is greater + the inversions of the remaining
(define (inversions l)
        (cond ((< (length l) 2) 0)
              (else (+ (length (filter (lambda (x) (> (car l) x)) (cdr l)))
                       (inversions (cdr l))))))

(use-modules (ice-9 rdelim))

(define (call-n-times proc n)
        (if (= 0 n)
            '()
            (cons (proc) (call-n-times proc (- n 1)))))

(define (solve)
        (write-line (inversions (call-n-times read (read)))))

(call-n-times solve (read))

有什么提示吗？

Answer 1

过滤超过一个非常长的列表，你可能会遇到最大的回溯错误(规格，最多一千万)，而不是使用‘(长度(过滤器.用褶皱

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
            (fold
              (lambda (init next)
                (if (> (car l) next)
                    (+ init 1)
                    init))
              0
              (cdr L)))
         (cdr L)))))

第二，这更容易理解，将折叠提取到它自己的功能中

(define (inversions-from-car L)
  (fold
     (lambda (init next)
        (if (> (car l) next)
            (+ init 1)
            init))
      0
      (cdr L)))

(define (inversion L)
 (let loop ((accumulator 0) (L L))
   (if (null? L)
       accumulator
       (loop 
         (+ accumulator
             (inversions-from-car L)     
         (cdr L)))))

这看起来是一个很好的处理数据结构的问题，因为正如所写的，它是n^2复杂性。

我想你可以把它降到n(log n)

假设在与左侧节点#配对的值列表上创建一个排序树。对于这组

'(2 3 8 6 1) -> '(1 2 3 6 8) -> 
(*tree (*entry 3 2 2)
       (*tree (*entry 2 1 1)
              (*tree (*entry 1 0 1)
                     ()
                     ())
              ())
        (*tree (*entry 8 1 1)
               (*tree (*entry 6 0 1)
                      ()
                      ())
               ()))      

*树和*条目只是类型，*树应该有一个条目，一个左和一个右*条目应该有一个值，#左和数字)

首先，用零累加器查找原始列表中的第一个

'(2 3 8 6 1)

如果enrty的值与第一个匹配，则将#左侧添加到累加器

如果值大于第一次，则在树的左分支上使用累加器进行递归。

如果条目的值小于第一，则在右侧分支上递归，并将#左侧添加到累加器中。

如果它是空树，抛出一个错误

那你需要更新树。

如果条目的值等于第一项，则对条目进行变异以将条目的数目减少一个。

如果值是entry，那么首先，对条目进行修改，将左减#减为1，然后在左分支上递归

如果条目的值小于第一项，则在右分支上递归

如果它是空树，抛出一个错误

可以将这些规则组合为单个遍历。

另外，如果#左侧为0，数字为0，则如果右分支为null，则将该树突变到空树中，否则为右分支。

以下是这个想法的粗略(未经测试的版本)

(define (rev-sorted-list->count-list L) ;;sort should be resverse of
                                        ;; final desired order
 (let loop ((value (car L)) (count 1) (L (cdr L)) (acc '()))
   (cond ((null? L) '())
         ((= value (car l))
          (loop value (+ 1 count) (cdr L) acc))
         (else 
          (loop (car l) 1 (cdr L) (cons (cons value count) acc))))))

(define (make-tree count c-L)
 (let* ((middle (ceiling (+ 1 count) 2))
        (left-count (- middle 1))
        (right-count (-count middle))
        (left (if (= 0 left-count)
                  null-tree 
                  (make-tree left-count c-L)))
        (entry+right
          (let loop ((index 1) (L c-L))
            (if (= index middle) 
                L
                (loop (+ 1 index) (cdr L)))))
        (entry 
         (make-entry 
           (caar entry+right)
           left-count
           (cdar entry+right))))
    (build-tree 
       entry
       left
       (if (= 0 right-count)
           null-tree
           (make-tree right-count (cdr entry+right))))))     

;;form left branches from starting points
;;;form right from stopping points
;;never mutating c-L or copies

;;if count = 0 then null tree

(define (build-tree entry left right)
  (list '*tree entry left right) 

(define (entry tree)
 (cadr tree)
(define (left-branch tree)
 (caddr tree))
(define (right-branch tree)
 (cadddr tree))

(define null-tree (list '*tree '()))
(define (null-tree? tree)
 (null? (entry tree)))

(define (make-entry value Nleft count)
 (let ((vec (make-vector 3)))
  (begin (vector-set! vec 0 value)
         (vector-set! vec 1 Nleft)
         (vector-set! vec 2 count)
         vec)))

;;might meessage passing function here

(define (entry-value entry)
 (vector-ref entry 0))

(define (entry-Nleft entry)
 (vector-ref entry 1))

(define (entry-Nleft-set! entry int)
 (vector-set! entry 1 int))

(define (entry-count entry)
 (vector-ref entry 2))

(define (entry-count-set! entry int)
 (vector-set! entry 2 int))

(define (inversions! Test-List Search-Tree)
 (let loop ((acc 0) (L Test-list) (T Search-tree))
   (cond ((null? L) acc)
         ((null-tree? T) (error "null tree " 
                                 "in inner loop of inversion!"))
         ((= (car L) (entry-value (entry T)))
          (entry-count-set! (entry T)
                            (- (entry-count (entry T)) 1))
          (if (and (= 0 (entry-count (entry T)))
                   (= 0 (entry-Nleft (entry T))))
               (set-cdr! T (right-branch T))
               'skip)
          (loop (+ acc (entry-Nleft (entry T)))
                (cdr L)
                Search-tree))
         ((< (car L) (entry-value (entry T)))
          (entry-Nleft-set! (entry T)
                            (- (entry-Nleft (entry T)) 1))
          (loop acc L (left-branch T)))
         ((> (car L) (entry-value (entry T)))
          (loop (+ acc (entry-Nleft (entry T)))
                L
                (right-branch T))))))