Div2
1 比較簡(jiǎn)單的一道題目，理清楚邏輯關(guān)系。。
2 trick的一道題目，真是惡心人啊。。。從下面的一張圖中來(lái)看出種種的關(guān)系。。比賽的時(shí)候，糾結(jié)了。。所以沒(méi)搞出來(lái)。。
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";
}
}
其中的邏輯關(guān)系還是很顯然的。。要淡定！。。。
看看某個(gè)房間里的情況。。唉，這告訴我們無(wú)論什么時(shí)候都不要放棄努力！
仔細(xì)和認(rèn)真，有一個(gè)端正的態(tài)度是做好一切事情的法寶！
3 這個(gè)第三題應(yīng)當(dāng)和第二題換一下啊。。非常簡(jiǎn)單。。
因?yàn)橐粋€(gè)人可能會(huì)有幾個(gè)job，但是一個(gè)job只能對(duì)應(yīng)于一個(gè)人。。這就使問(wèn)題變得非常簡(jiǎn)單了。。很easy的會(huì)想到每個(gè)人的job duration和來(lái)做排序。。如果job duration 和相同，就以第一個(gè)首元素做排序標(biāo)準(zhǔn)。。
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;
}
};
剛開(kāi)始的時(shí)候，以為這個(gè)題目中，一個(gè)job可以對(duì)應(yīng)于幾個(gè)人的情況。。實(shí)在是不應(yīng)該啊。。
===========================================================================================
不是很華麗的分割線。。。
===========================================================================================
DIV1
1 DIV2 500的題目，照例的惡心。。。
2 基于DIV900的那個(gè)理論，然后這次是求期望等待時(shí)間，需要分階段來(lái)討論。首先是在此人之前的人，其次是具有相同優(yōu)先級(jí)的人，再次是這個(gè)人的不同工作之間。。總之，也是一個(gè)比較簡(jiǎn)單的題目。
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 忘了什么意思了。。有時(shí)間貼出來(lái)。
Reference ： 參考了SRM 481的解題報(bào)告和 best solution。。。代碼都是大大們寫(xiě)的。。。學(xué)習(xí)！