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";
    }
}

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

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

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

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。。。代碼都是大大們寫的。。。學習！