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。。。代码都是大大们写的。。。学习！