• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217940
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            解題報告:http://www.mydrs.org/program/list.asp?id=583

            Bridging Signals

            Time limit: 1 Seconds?? Memory limit: 32768K??
            Total Submit: 946?? Accepted Submit: 495??

            'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

            Figure 1. To the left: The two blocks' ports and their signal mapping (4, 2, 6, 3, 1, 5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.

            A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the ith number specifies which port on the right side should be connected to the ith port on the left side. Two signals cross if and only if the straight lines connecting the two ports of each pair do.


            Input

            On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p < 40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping:

            On the ith line is the port number of the block on the right side which should be connected to the ith port of the block on the left side.


            Output

            For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.


            Sample Input

            4
            6
            4
            2
            6
            3
            1
            5
            10
            2
            3
            4
            5
            6
            7
            8
            9
            10
            1
            8
            8
            7
            6
            5
            4
            3
            2
            1
            9
            5
            8
            9
            2
            3
            1
            7
            4
            6

            Sample Output

            3
            9
            1
            4

            #include? < iostream>
            using
            ? namespace?std;

            const ? int ?MAXN? = ? 40001;

            void?Solve()
            {
            ????
            int?n;
            ????
            int?i,?j,?k;
            ????
            int?l,?r,?m;
            ????
            int?t;
            ????
            int ?d[MAXN]? = ? { 0 };
            ????
            int?a[MAXN];
            ????
            int ?len? = ? 0;
            ????scanf(
            " %d " ,? &n);
            ????
            for ?(i = 1 ;?i <= n;?i ++)?
            ????????scanf(
            " %d " ,? &a[i]);
            ????
            for ?(i = 1 ;?i <= n;?i ++)
            ????
            {
            ????????
            if ?(a[i]? >?d[len])
            ????????
            {
            ????????????len?
            += ? 1;
            ????????????d[len]?
            =?a[i];
            ????????}

            ????????
            else
            ????????
            {
            ????????????l?
            = ? 1;
            ????????????r?
            =?len;
            ????????????
            while ?(l? < ?r? - ? 1)
            ????????????
            {
            ????????????????m?
            = ?(l? + ?r)? / ? 2;
            ????????????????
            if ?(d[m]? <?a[i])
            ????????????????????l?
            =?m;
            ????????????????else
            ????????????????????r?
            =?m;
            ????????????}

            ????????????if
            ?(d[l]?>?a[i])?
            ????????????????d[l]?
            =?a[i];
            ????????????else
            ????????????????d[r]?
            =?a[i];
            ????????}

            ????}

            ????printf("
            %d\n ",?len);????????
            }



            int?main()
            {
            ????
            int?caseTime;
            ????scanf(
            " %d " ,? &caseTime);
            ????
            while ?(caseTime -- ? != ? 0)
            ????
            {
            ????????Solve();
            ????}

            ????system("pause
            ");
            ????
            return ?0;
            }






            posted on 2006-10-04 12:20 閱讀(585) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            久久综合五月丁香久久激情| 欧美色综合久久久久久| 久久久久久久91精品免费观看| 亚洲国产精品久久久久婷婷老年| 久久国产综合精品五月天| 99久久综合狠狠综合久久| 亚洲国产小视频精品久久久三级| 午夜精品久久久久久99热| 国产一区二区精品久久| 久久丝袜精品中文字幕| 精品久久久无码人妻中文字幕豆芽| 国产呻吟久久久久久久92| 亚洲午夜久久久久久久久电影网| 99久久综合狠狠综合久久止| 久久综合久久鬼色| 四虎国产精品免费久久5151| 偷窥少妇久久久久久久久| 国产精品伊人久久伊人电影| 国产综合久久久久久鬼色| 亚洲性久久久影院| 国产免费久久精品99久久| av无码久久久久不卡免费网站 | 91久久精品无码一区二区毛片| 欧美久久一级内射wwwwww.| 国产精品久久久久久搜索| 亚洲AV无码成人网站久久精品大| 久久有码中文字幕| 久久av免费天堂小草播放| 国产一区二区三区久久精品| 人妻少妇久久中文字幕一区二区| 亚洲午夜无码AV毛片久久| 久久久久久毛片免费看| 久久精品成人免费网站| 亚洲AV无码成人网站久久精品大| 亚洲国产综合久久天堂| 欧美一级久久久久久久大| 国产精品99久久久久久宅男| 久久99热精品| 久久婷婷五月综合97色直播| 久久国产乱子伦精品免费午夜| 亚洲成人精品久久|