• <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)  編輯 收藏 引用

            統計系統
            日韩精品久久无码中文字幕| 性欧美大战久久久久久久久| 国产精品美女久久久m| 久久一本综合| 亚洲精品无码成人片久久| 久久久久亚洲AV片无码下载蜜桃| 一本久久a久久精品vr综合| 亚洲精品无码久久久久久| 国产精品福利一区二区久久| 国产精品久久久久影院嫩草 | 久久精品麻豆日日躁夜夜躁| 人人狠狠综合久久88成人| 亚洲国产天堂久久综合网站| 午夜精品久久久内射近拍高清| 国产成人久久精品一区二区三区| 国产精品久久久久aaaa| 亚洲欧美日韩久久精品| 久久精品一本到99热免费| 久久午夜福利电影| 精品久久久久久中文字幕| 麻豆久久久9性大片| 久久福利青草精品资源站| 日本加勒比久久精品| 国产成人久久激情91| 久久精品久久久久观看99水蜜桃| 久久综合丝袜日本网| 亚洲va国产va天堂va久久| 久久精品国产亚洲一区二区三区| 久久人人爽爽爽人久久久| 久久久久99这里有精品10| 亚洲一区二区三区日本久久九| 97精品依人久久久大香线蕉97| 久久久久国产日韩精品网站| 久久青草国产手机看片福利盒子| 久久SE精品一区二区| 中文字幕精品无码久久久久久3D日动漫 | 久久国产精品视频| 久久综合九色综合久99| 久久99精品久久久久婷婷| 亚洲国产一成人久久精品| 精品国产乱码久久久久久人妻 |