• <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 閱讀(276) 評論(0)  編輯 收藏 引用

            統計系統
            天天爽天天狠久久久综合麻豆| 久久线看观看精品香蕉国产| 伊人久久综在合线亚洲2019| 久久99精品久久久久久水蜜桃| 蜜桃麻豆www久久国产精品| 久久只有这精品99| 久久精品国产清高在天天线| 久久精品中文字幕一区| 久久精品国产亚洲AV无码麻豆| 久久香蕉国产线看观看精品yw| 久久精品二区| 伊人久久精品无码av一区| 国内精品久久久久国产盗摄| 欧美伊人久久大香线蕉综合| 香蕉久久永久视频| 久久www免费人成精品香蕉| 亚洲日韩中文无码久久| 国产精品99久久久久久董美香| 国产精品久久久久久福利漫画 | 久久免费线看线看| 中文字幕久久亚洲一区| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久精品成人欧美大片| 国产一级持黄大片99久久| 欧美午夜精品久久久久免费视| 91久久精品国产91性色也| 精品久久久久中文字幕日本| 久久天堂AV综合合色蜜桃网| 欧美亚洲国产精品久久久久| 日本道色综合久久影院| 精品无码久久久久久午夜| 亚洲精品无码久久久久| 久久亚洲国产精品123区| 国产午夜精品理论片久久| 99久久综合狠狠综合久久| 93精91精品国产综合久久香蕉 | 欧美粉嫩小泬久久久久久久| 国产成人AV综合久久| 国产午夜精品理论片久久 | 欧美亚洲色综久久精品国产| 亚洲AV无码一区东京热久久|