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

            O(1) 的小樂

            Job Hunting

            公告

            記錄我的生活和工作。。。
            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            統計

            • 隨筆 - 182
            • 文章 - 1
            • 評論 - 41
            • 引用 - 0

            留言簿(10)

            隨筆分類(70)

            隨筆檔案(182)

            文章檔案(1)

            如影隨形

            搜索

            •  

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            SRM 481

            Div2

            1 比較簡單的一道題目,理清楚邏輯關系。。

            2 trick的一道題目,真是惡心人啊。。。從下面的一張圖中來看出種種的關系。。比賽的時候,糾結了。。所以沒搞出來。。

            In the graphic, c + y will be equal to x (The total number of people that told you the correct answer) and a+b will be equal to n-x (The total number of people that told you the wrong answer). Since we know the number of elements in LIARS (liarCount) and the number of people in the intersection is assumed to be y we can conclude that a=lieCount-y. Similarly, b = liarCount-y. Since all the other literals are known, c = n - a - b - y. Knowing a, b, c and y we can verify: If (a+b) is equal to (n-x) and (c+y = x) then the scenario is possible. There is an implicit condition, an important one that was missed by many during the match, we do not want y to be so small, that the sum a+b-y is larger than n, this case can be detected by making sure that c is positive. Also note that since the numbers in the input can only be as large as 1000000, we can simply iterate through all the possible values of y until one for which the previous conditions hold.
            We can then code a solution:

            // Is the following scenario possible?:
            //
            // n people.
            // x people told the truth.
            // lieCount people were lied to.
            // liarCount people lied intentionally
            //
            boolean check(int n, int x, int lieCount, int liarCount) {
                // Iterate through all the possible values of the intersection y:
                for (int y = 0; y <= lieCount && y <= liarCount; y++) {
                    int a = lieCount - y;
                    int b = liarCount - y;
                    int c = n - a - b - y;
            
                    // Do all the required conditions hold?
                    if ( a+b==n-x && c+y==x && c>=0 ) {
                        return true;
                    }
                }
                return false;
            }
            //
            
            public String theTruth(int n, int eggCount, int lieCount, int liarCount) {
                // Call the sub-routine, first assuming that the egg is the correct answer
                boolean egg =     check(n,eggCount, lieCount, liarCount );
                // Then assuming that the chicken is the correct answer:
                boolean chicken = check(n,n-eggCount, lieCount, liarCount );
                if(egg&&chicken) {
                    return "Ambiguous";
                } else if (egg) {
                    return "The egg";
                } else if (chicken) {
                    return "The chicken";
                } else {
                    return "The oracle is a lie";
                }
            }
             

            其中的邏輯關系還是很顯然的。。要淡定!。。。

            QQ截圖未命名

            看看某個房間里的情況。。唉,這告訴我們無論什么時候都不要放棄努力!

            仔細和認真,有一個端正的態度是做好一切事情的法寶!

            3 這個第三題應當和第二題換一下啊。。非常簡單。。

              因為一個人可能會有幾個job,但是一個job只能對應于一個人。。這就使問題變得非常簡單了。。很easy的會想到每個人的job duration和來做排序。。如果job duration 和相同,就以第一個首元素做排序標準。。

            map <string,int> mp;
            struct str{
                   long long tot;
                   int num;
                   int next[55];
            };
            str st[55];
            bool operator <(str a, str b)
            {
                 if (a.tot != b.tot)
                    return a.tot < b.tot;
                 return a.next[0] < b.next[0];
            }
            class BatchSystem
            {
                    public:
                    vector <int> schedule(vector <int> duration, vector <string> user)
                    {
                           int n = duration.size();
                           int i,j,t;
                           int ct = 0;
                           memset(st,0,sizeof(st));
                           mp.clear();
                           for (i = 0;i < n;i++)
                           {
                               if (mp.find(user[i]) == mp.end())
                                  mp[user[i]] = ct++;
                               t = mp[user[i]];
                               st[t].tot += duration[i];
                               st[t].next[st[t].num++] = i;
                           }
                           sort(st,st + ct);
                           vector <int> ans;
                           ans.clear();
                           for (i = 0;i < ct;i++)
                           {
                               for (j = 0;j < st[i].num;j++)
                                   ans.push_back(st[i].next[j]);
                           }
                           return ans;
                    }
            };

            剛開始的時候,以為這個題目中,一個job可以對應于幾個人的情況。。實在是不應該啊。。

             

             

             

            ===========================================================================================

            不是很華麗的分割線。。。

            ===========================================================================================

            DIV1

            1 DIV2 500的題目,照例的惡心。。。

            2 基于DIV900的那個理論,然后這次是求期望等待時間,需要分階段來討論。首先是在此人之前的人,其次是具有相同優先級的人,再次是這個人的不同工作之間。。總之,也是一個比較簡單的題目。

            vector <double> expectedFinishTimes(vector <int> duration, vector <string> user)
            {
                int n = duration.size();
                // Find users and their total durations:
                map<string, long long> userDuration;
                for (int i=0; i<n; i++) {
                    userDuration[user[i]]+=duration[i];
                }
                vector<double> res(n);
                for (int i=0; i<n; i++) {
                    int eqn = 0;
                    double before = 0;
                    // For each pair user, total duration:
                    //   * count the number of users with the same
                    //     total duration (eqn).
                    //   * Accumulate the total duration from users
                    //     with smaller total duration (before).
                    for ( map<string,long long>::iterator it = userDuration.begin();
                          it!=userDuration.end(); it++) {
            
                        if (it->second < userDuration[user[i]] ) {
                            before += it->second;
                        } else if ( it->second == userDuration[user[i]] ) {
                            eqn ++;
                        }
                    }
                    // The time this process will have to wait is:
                    //  before :
                    //      The waiting time caused by users with lower total durations.
                    // + (eqn-1) * userDuration[user[i]] / 2.0 :
                    //      The expected waiting time caused by users with the same total duration.
                    //
                    // + (userDuration[user[i]]-duration[i]) / 2.0 :
                    //      The expected waiting time caused by jobs from the same user.
                    //
                    // + duration[i]:
                    //      The job's duration
                    res[i] = before
                             + (eqn-1) * userDuration[user[i]] / 2.0
                             + (userDuration[user[i]]-duration[i]) / 2.0
                             + duration[i];
                }
                return res;
            }
             
            3 忘了什么意思了。。有時間貼出來。
            Reference : 參考了SRM 481的解題報告和 best solution。。。代碼都是大大們寫的。。。學習!
             

            posted on 2010-09-12 17:41 Sosi 閱讀(277) 評論(0)  編輯 收藏 引用

            統計系統
            久久精品国产亚洲αv忘忧草| 国产三级观看久久| 热99RE久久精品这里都是精品免费 | 香蕉99久久国产综合精品宅男自| 一级做a爰片久久毛片免费陪| 久久香蕉国产线看观看精品yw| 久久精品麻豆日日躁夜夜躁| 国产精品免费久久久久电影网| 亚洲伊人久久成综合人影院| 久久超碰97人人做人人爱| 久久青青国产| 国产欧美久久久精品| 性做久久久久久久久| 国产精品久久久久久久久免费| 无码8090精品久久一区| 国产精品久久久久久| 综合久久国产九一剧情麻豆| 久久国产精品偷99| 久久精品国产亚洲网站| 久久人人添人人爽添人人片牛牛| 99精品伊人久久久大香线蕉| 久久久久国产精品熟女影院 | 久久久久久精品免费看SSS| 伊人色综合久久天天| 国内精品久久久久伊人av| 久久AV无码精品人妻糸列| 久久久久亚洲AV无码去区首| 久久久精品一区二区三区| 久久w5ww成w人免费| 一本久久a久久精品vr综合| 一级女性全黄久久生活片免费| 狠狠色伊人久久精品综合网| 韩国三级大全久久网站| 国产成人精品白浆久久69| 人妻久久久一区二区三区| 久久99精品国产麻豆宅宅| 漂亮人妻被中出中文字幕久久 | 2020久久精品国产免费| 久久水蜜桃亚洲av无码精品麻豆| 精品国产乱码久久久久久呢 | 成人国内精品久久久久影院VR|