合并区间

aimisiyou

题目如图，可理解为已知y=f(x)，求对于任一k值，求x的连续最大区间，使得对于区间内的任意x有f(x)>=k。区间可以有多个。

aimisiyou

(setq lst '(1 3 3 5 5 7 7 4 4 3 3 3 1 1 2 2 2 4 4 4 2 0 1 0 1 0 1 0 1) n (length lst) num_max (apply 'max lst))
(defun fnlst (nn)
  (setq ii nn nn_lst nil)
  (while (> ii 0)
      (setq ii (- ii 1))
      (setq nn_lst (cons ii nn_lst))
   )
)
(setq vlst (mapcar 'list (fnlst n) lst))
(mapcar '(lambda (x)
             (entmake
                             (list
                                  '(0 . "LWPOLYLINE")                        
                                  '(100 . "AcDbEntity")
                                  '(100 . "AcDbPolyline")
                                  '(90 . 4)                                 
                                  '(70 . 1)                                 
                                  (cons 10 (list (car x) 0))
                                  (cons 10 (list (+ (car x) 1) 0))
                                  (cons 10 (list (+ (car x) 1) (cadr x)))
                                  (cons 10  x)            
                                  (cons 210 '(0 0 1))   
                               )                     
                      )
                         )
                         vlst
)


(setq i 1 zzlst nil)
(while (< i n)
  (setq valst (apply 'append (vl-remove nil (mapcar '(lambda (x) (if (>= (car x) i) (list (cadr x) (+ 1 (cadr x))) nil))    (mapcar 'reverse vlst)))) nn (length valst))
  (setq vblst (vl-remove nil (mapcar '(lambda (x) (if (= (car x) 1) x nil)) (mapcar '(lambda (y) (list (- nn (length    (vl-remove y valst))) y))  (vl-sort valst '<)))))
  (repeat (/ (length vblst) 2)
    (setq zzlst (cons (list (cadr (car vblst)) (cadr (cadr vblst)) (+ i num_max)) zzlst))
    (setq vblst (cdr (cdr vblst)))
   )
   (setq i (+ 1 i))
)
(mapcar '(lambda (x)
             (entmake
                             (list
                                  '(0 . "LWPOLYLINE")                        
                                  '(100 . "AcDbEntity")
                                  '(100 . "AcDbPolyline")
                                  '(90 . 4)                                 
                                  '(70 . 1)                                 
                                  (cons 10 (list (car x) (- (caddr x) 1)))
                                  (cons 10 (list (cadr x) (- (caddr x) 1)))
                                  (cons 10 (list (cadr x) (caddr x)))
                                  (cons 10  (list (car x) (caddr x)))            
                                  (cons 210 '(0 0 1))   
                               )                     
                      )
                         )
                        zzlst
)

zhystar

楼主好厉害啊，问一下，这是解决什么问题

aimisiyou

zhystar 发表于 2020-2-11 11:06
楼主好厉害啊，问一下，这是解决什么问题

别人问的一个数据分析上的问题，刚好与图形有关，就顺便用lisp实现输入数据自动出图。

aimisiyou

核心问题就是区间合并算法，如果用（i  j）表示[i,j)
左闭右开区间，如何合并？如lst=((1  2)(2  4)(5  7)(7 9)(10   13))合并的结果是((1  4)(5  9)(10  13))。当然，这是各小区间没有重叠的情况，如果有重叠处理就复杂些。对于没有重叠的情况很好处理，将lst合并得到lst'=(1 2 2 4 5 7 7 9 10 13)，然后统计每个数出现的次数，用(ai,ni)表示，即lst"=((1 1)(2 2)(4  1)(5   1)(7   2)(9  1)(10  1)(13  1)),仅找次数ni为1的项，从左到右，两个一配对(ai  aj)，记即得((1  4)(5   9)(10   13))。

tzfcn

高手如云呀。

yuren008

做个对论坛有益的人。