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：

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "BatchSystemRoulette.cpp"

 #include <cstdlib>

 #include <cctype>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <fstream>

 #include <numeric>

 #include <iomanip>

 #include <bitset>

 #include <list>

 #include <stdexcept>

 #include <functional>

 #include <utility>

 #include <ctime>

 using namespace std;

 #define PB push_back

 #define MP make_pair

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int, int> PII;

 struct oo{

        int val, id;

        string usr;

        oo(){}

        oo(int _val, int _id, string _usr): val(_val), id(_id), usr(_usr){}

        bool operator<(const oo &b)const{

              return usr < b.usr || (usr == b.usr && val < b.val);

        }

 };

 int P[], S[], last[];

 long long sum[];

 class BatchSystemRoulette

 {

         public:

         vector <double> expectedFinishTimes(vector <int> dur, vector <string> user)

         {

                 vector<oo> v;

                 v.clear();

                 for (int i = ; i < dur.size(); ++i)

                    v.push_back(oo(dur[i], i, user[i]));

                 sort(v.begin(), v.end());

                 int n = v.size();

                 memset(sum, , sizeof(sum));

                 memset(P, , sizeof(P));

                 int m = ;

                 sum[] = v[].val;

                 P[] = ;

                 for (int i = ; i < n; ++i){

                     if (v[i].usr != v[i-].usr) m++;

                     sum[m] += v[i].val;

                     P[i] = m;

                 }

                 last[m] = n - ;

                 memset(S, , sizeof(S));

                 for (int i = ; i <= m; ++i)

                     for (int j = ; j <= m; ++j)

                         if (sum[i] == sum[j]) S[i]++;

                 vector<double> ans(n);

                 for (int i = ; i < n; ++i){

                      double ssum = ;

                      for (int j = ; j <= m; ++j)

                          if (sum[P[i]] > sum[j]) ssum += sum[j];

                      double tmp = (S[P[i]] - 1.0) / 2.0 * sum[P[i]];

                      tmp += 0.5 * (sum[P[i]] - v[i].val) + v[i].val;

                      ans[v[i].id] = tmp + ssum;

                 }

                 return ans;

         }

 };

相关文章