SRM481

250pt

题意：上帝知道一个“先有鸡还是先有蛋”的答案，上帝和N<=10^6个人说了答案，不过有x个人故意告诉了他们错误的答案，然后有一个人问了这N个人问题的答案，有M个人说先有鸡，N-M个人说现有蛋，已知其中有y个人故意说了上帝告诉他们的相反的答案。现在给N M x y，问是否能推测出答案，或者多解，或者无解。

思路：因为N很小，直接枚举那些人说谎，然后判定即可。

500pt

题意：有N<=50个任务，每个任务有运行时间和用户，机器同一个时间只能跑一个任务，一个任务运行中不能中断，每个用户可能有多个任务，每个用户的等待时间为他的最后一个任务完成前等待的时间。电脑安排任务始终保证所有用户的平均等待时间最短，在这个条件下，每个schedule都有同等的可能性。现在给你N个任务的信息，问每个任务期望的结束时间是多少。

思路：很明显，对于某个人的任务，那么一定是连着运行对于结果最优。

那么那么如果a与b的任务运行时间相同，那么他们两个是可以交换的。

同时，对于同一user的任务间，顺序任意。接下去便是统计了。注意任务是等概率的就好做了。

code：

 1 // BEGIN CUT HERE
 2 /*
 3 
 4 */
 5 // END CUT HERE
 6 #line 7 "BatchSystemRoulette.cpp"
 7 #include <cstdlib>
 8 #include <cctype>
 9 #include <cstring>
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13 #include <vector>
14 #include <string>
15 #include <iostream>
16 #include <sstream>
17 #include <map>
18 #include <set>
19 #include <queue>
20 #include <stack>
21 #include <fstream>
22 #include <numeric>
23 #include <iomanip>
24 #include <bitset>
25 #include <list>
26 #include <stdexcept>
27 #include <functional>
28 #include <utility>
29 #include <ctime>
30 using namespace std;
31 
32 #define PB push_back
33 #define MP make_pair
34 
35 typedef vector<int> VI;
36 typedef vector<string> VS;
37 typedef vector<double> VD;
38 typedef long long LL;
39 typedef pair<int, int> PII;
40 struct oo{
41        int val, id;
42        string usr;
43        oo(){}
44        oo(int _val, int _id, string _usr): val(_val), id(_id), usr(_usr){}
45        bool operator<(const oo &b)const{
46              return usr < b.usr || (usr == b.usr && val < b.val);
47        }
48 };
49 int P[120], S[120], last[120];
50 long long sum[120];
51 class BatchSystemRoulette
52 {
53         public:
54         vector <double> expectedFinishTimes(vector <int> dur, vector <string> user)
55         {
56                 vector<oo> v;
57                 v.clear();
58                 for (int i = 0; i < dur.size(); ++i)
59                    v.push_back(oo(dur[i], i, user[i]));
60                 sort(v.begin(), v.end());
61                 int n = v.size();
62                 memset(sum, 0, sizeof(sum));
63                 memset(P, 0, sizeof(P));
64                 int m = 1;
65                 sum[1] = v[0].val;
66                 P[0] = 1;
67                 for (int i = 1; i < n; ++i){
68                     if (v[i].usr != v[i-1].usr) m++;
69                     sum[m] += v[i].val;
70                     P[i] = m;
71                 }
72                 last[m] = n - 1;
73                 memset(S, 0, sizeof(S));
74                 for (int i = 1; i <= m; ++i)
75                     for (int j = 1; j <= m; ++j)
76                         if (sum[i] == sum[j]) S[i]++;
77                 vector<double> ans(n);
78                 for (int i = 0; i < n; ++i){
79                      double ssum = 0;
80                      for (int j = 1; j <= m; ++j)
81                          if (sum[P[i]] > sum[j]) ssum += sum[j];
82                      double tmp = (S[P[i]] - 1.0) / 2.0 * sum[P[i]];
83                      tmp += 0.5 * (sum[P[i]] - v[i].val) + v[i].val;
84                      ans[v[i].id] = tmp + ssum;
85                 }
86                 return ans;
87         }
88 };

View Code