• <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>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            SRM549 DIVⅡ 500pt(最大匹配)

            Problem Statement

                 The Order of All Things Pointy and Magical has commissioned the creation of some new wizard hats. A wizard hat is created by taking two cones: a decorative top cone, and a warm and fluffy bottom cone. To assemble the hat, both cones are first placed onto a table, so that their bases are horizontal and their apexes point upwards. The top cone is then lifted and placed onto the bottom cone. The base of the top cone has to remain horizontal, and the apex of the top cone must be strictly above the apex of the bottom cone.

            Not every pair of cones can be used to create a wizard hat. A wizard hat is only produced if the following two criteria are both met:
            • The apex of the top cone must be strictly above the apex of the bottom cone. I.e., when the top cone is placed on top of the bottom cone and released, their apexes must not touch.
            • Some part of the bottom cone must remain visible to form the brim of the hat. (Otherwise, the hat would look like a simple cone, not like a wizard hat!)
            You have several top cones and several bottom cones of various sizes. Each cone can be described by its height (the distance between the apex and the base) and by the radius of its base. The top cones you have are described by topHeight and topRadius: for each valid i, you have one top cone with height topHeight[i] and radius topRadius[i]. The bottom cones you have are described by bottomHeight and bottomRadius in the same way.

            Your task is to determine the maximum number of wizard hats you can make using each of the available top and bottom cones at most once.

            Definition

                
            Class: PointyWizardHats
            Method: getNumHats
            Parameters: vector <int>, vector <int>, vector <int>, vector <int>
            Returns: int
            Method signature: int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius)
            (be sure your method is public)
                

            Constraints

            - topHeight and topRadius will contain the same number of elements.
            - bottomHeight and bottomRadius will contain the same number of elements.
            - topHeight will contain between 1 and 50 elements, inclusive.
            - topRadius will contain between 1 and 50 elements, inclusive.
            - bottomHeight will contain between 1 and 50 elements, inclusive.
            - bottomRadius will contain between 1 and 50 elements, inclusive.
            - Each element of topHeight, topRadius, bottomHeight, and bottomRadius will be between 1 and 10,000, inclusive.

            Examples

            0)
                
            {30}
            {3}
            {3}
            {30}
            Returns: 1
            The top and bottom cone can be used together to make a wizard hat.
            1)
                
            {4,4}
            {4,3}
            {5,12}
            {5,4}
            Returns: 1
            The only way to produce a wizard hat is to use the top cone 1 (height 4, radius 3) and the bottom cone 0 (height 5, radius 5).
            2)
                
            {3}
            {3}
            {1,1}
            {2,4}
            Returns: 1

            3)
                
            {10,10}
            {2,5}
            {2,9}
            {3,6}
            Returns: 2

            4)
                
            {3,4,5}
            {5,4,3}
            {3,4,5}
            {3,8,5}
            Returns: 2

            5)
                
            {1,2,3,4,5}
            {2,3,4,5,6}
            {2,3,4,5,6}
            {1,2,3,4,5}
            Returns: 0

            6)
                
            {123,214,232,323,342,343}
            {123,123,232,123,323,434}
            {545,322,123,545,777,999}
            {323,443,123,656,767,888}
            Returns: 5

            7)
                
            {999,999,999,10000,10000,10000}
            {10000,10000,10000,1,2,3}
            {2324,2323,234,5454,323,232}
            {1,2,3222,434,5454,23}
            Returns: 3


            This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.





            題意:一個hat由上面top cone和下面的bottom cone組成。給定上面cone的高和底半徑,topHeigh[],topRadius[]下面cone的bottomHeight[],bottomRadius[]
                     上下兩個cone組成hat需要滿足條件:
                              1:The apex of the top cone must be strictly above the apex of the bottom cone. I.e., when the top cone is placed on top of the bottom cone and released, their apexes must not touch.
                              2:Some part of the bottom cone must remain visible to form the brim of the hat. (Otherwise, the hat would look like a simple cone, not like a wizard hat!)


            思路:求二分圖的最大匹配,模版題。
                     topcone 和bottomcone滿足的條件是:topR<bottomR && topR*bottomH<topH*bottomR

            錯誤提交了一次,尼瑪!!!猶豫不決不敢coding不行呀!!

            175.22pt
                          
            #include<stdio.h>
            #include
            <string>
            #include
            <vector>
            #include
            <algorithm>
            using namespace std;
            bool map[55][55];
            int result[55];
            bool state[55];
            int n,m;
            class PointyWizardHats{
            public:
                
            int find(int x)
                {
                    
            int i;
                    
            for (i=0;i<m ;i++ )
                    {
                        
            if (map[x][i]==1 && !state[i])
                        {
                            state[i]
            =1;
                            
            if (result[i]==-1 || find(result[i]))
                            {
                                result[i]
            =x;
                                
            return 1;
                            }
                        }
                    }
                    
            return 0;
                }
                
            bool can(int x1,int y1,int x2,int y2) //這個條件我猶豫了半天,thinking不夠啊!
                {
                    
            if (y2*x1>y1*x2 && y2>y1)
                        
            return 1;
                    
            return 0;
                }
                
            int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius){

                    
            int i,j;
                    
            int ans;
                    n
            =topHeight.size();
                    m
            =bottomHeight.size();
                    memset(map,
            0,sizeof(map));
                    
            for (j=0;j<m;j++)
                        result[j]
            =-1;    //這里之前全部設置的0啊啊啊!!!
                    
            for (i=0;i<n;i++)
                        
            for (j=0;j<m;j++)
                            
            if (can(topHeight[i],topRadius[i],bottomHeight[j],bottomRadius[j]))
                                map[i][j]
            =1;
                    ans
            =0;
                    
            for (i=0;i<n;i++)
                    {
                        memset(state,
            0,sizeof(state));
                        
            if (find(i))
                            ans
            ++;
                    }
                    
            return ans;
                }
            };



            posted on 2012-07-10 09:14 wangs 閱讀(272) 評論(0)  編輯 收藏 引用 所屬分類: Topcoder

            老男人久久青草av高清| 久久精品国产亚洲综合色| 欧美大战日韩91综合一区婷婷久久青草| 久久Av无码精品人妻系列| 久久久一本精品99久久精品66| 久久久久久久综合日本亚洲| 日韩久久久久中文字幕人妻 | 久久久久亚洲AV无码永不| 久久国产高清字幕中文| 香蕉99久久国产综合精品宅男自| 久久午夜羞羞影院免费观看| 久久艹国产| 国产精品对白刺激久久久| 久久久久无码国产精品不卡| 久久久久久久人妻无码中文字幕爆| 久久久久久国产精品美女| 久久久久无码精品国产不卡| 亚洲国产成人精品女人久久久 | 亚洲va久久久噜噜噜久久狠狠| 亚洲国产精品无码久久久秋霞2 | 综合久久精品色| 欧美综合天天夜夜久久| 久久亚洲AV成人无码电影| 伊人色综合九久久天天蜜桃| 狠狠色综合久久久久尤物 | 久久久久久极精品久久久| 狠狠色婷婷综合天天久久丁香| 无码精品久久久天天影视 | 99久久国产精品免费一区二区| 久久天天躁狠狠躁夜夜不卡| 亚洲国产二区三区久久| 久久精品国产99久久无毒不卡| 久久人人爽人人人人片av| 亚洲国产天堂久久综合| 久久嫩草影院免费看夜色| 狠狠久久综合伊人不卡| 精品久久久无码中文字幕| 色综合久久88色综合天天 | 久久91这里精品国产2020| 久久99精品久久久久久齐齐 | 激情五月综合综合久久69|