• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            syhd142  
            日歷
            <2025年8月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456
            統(tǒng)計(jì)
            • 隨筆 - 23
            • 文章 - 122
            • 評(píng)論 - 31
            • 引用 - 0

            導(dǎo)航

            常用鏈接

            留言簿(2)

            隨筆檔案(23)

            文章分類(lèi)(270)

            文章檔案(122)

            我的豆瓣

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

             
            最長(zhǎng)遞增子序列的O(nlogn)算法,用一個(gè)數(shù)組a[i]表述當(dāng)前序列長(zhǎng)度為i時(shí)末尾元素的最小值。
            這樣當(dāng)輸入一個(gè)數(shù)時(shí),如果它比a[i-1]大,就直接添加到a[i],否則就在a[i]中進(jìn)行二分查找到該元素的位置(因?yàn)閍[i]是單調(diào)遞增的)。
            另外二分的時(shí)候需要注意別陷入死循環(huán)了。
            #include <stdio.h>
            #include 
            <string.h>

            #define N 40005

            int a[N];

            int main()
            {
                
            int t, tt, n, l;
                scanf(
            "%d\n"&t);
                
            while(t--)
                {
                    scanf(
            "%d"&n);
                    scanf(
            "%d"&tt);
                    memset(a, 
            0sizeof(a));
                    a[
            0= tt;
                    l 
            = 1;
                    
            for(int i = 1; i < n; i++)
                    {
                        scanf(
            "%d"&tt);
                        
            if(a[l - 1< tt) a[l++= tt;
                        
            else
                        { 
                            
            int left = 0, right = l - 1, mid = (left + right) >> 1;
                            
            while(left < right)
                            {
                                
            if(a[mid] < tt) left = mid + 1;
                                
            else if (a[mid] > tt) right = mid;
                                mid 
            = (left + right) >> 1;
                            }
                            a[mid] 
            = tt;
                        }
                    }
                    printf(
            "%d\n", l);
                }
                
            return 0;
            }
            posted on 2010-06-06 21:46 Fucker 閱讀(118) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): ACM/ICPCDP
             
            Copyright © Fucker Powered by: 博客園 模板提供:滬江博客
            久久综合亚洲鲁鲁五月天| 国产精品久久久久久久午夜片| 久久无码中文字幕东京热| 国产成人精品三上悠亚久久| 91精品国产高清久久久久久91| 亚洲AV无码久久精品蜜桃| 久久久久久久久66精品片| 三级韩国一区久久二区综合| 99久久国产主播综合精品 | 精品久久一区二区| 亚洲精品无码久久一线| 很黄很污的网站久久mimi色| 精品久久久久久国产91| 久久久精品国产免大香伊| 久久乐国产综合亚洲精品| 久久精品无码一区二区三区| 国产亚洲精品久久久久秋霞| 久久综合精品国产一区二区三区| 久久久久18| 精品久久久久久国产| 老司机午夜网站国内精品久久久久久久久 | 久久国产精品99精品国产| 久久国产高潮流白浆免费观看| 久久国产成人| 国产69精品久久久久9999| 97久久精品国产精品青草| 99国内精品久久久久久久| 精品久久久久久国产潘金莲| 国产精自产拍久久久久久蜜| 久久精品中文字幕无码绿巨人| 久久国内免费视频| 久久99热这里只频精品6| 久久精品无码一区二区三区日韩| 亚洲一本综合久久| 91久久成人免费| 国产成人久久777777| 99久久精品国产毛片| 色欲综合久久躁天天躁| 思思久久好好热精品国产| 欧美一区二区久久精品| 伊人久久大香线蕉亚洲五月天|