一晃好多年，我终于爬回了D1，可是今天这场不怎么好过……NA LIB的无线果然不好使……断了两次……
其实250没做出来也不怪它……逻辑性好强……我没想清楚……唉……不早了，明天再想……
唯一值得庆幸的是最后过了500，虽然比赛规定时间内没完成，不过思路差不多对了，只是算法细节上要注意好多……
500是道概率题
问题是给你一条流水线，有n个job要做，但只有一台机器，每次只能做一个job。每个job都有需要的时间以及请求这个job的人。这个系统很聪明，他会schedule一套方案来让所有请求job的人（注意是人）等的时间的平均值最少。如果有几种方案，取任意一种。求的却是每个job完成时间的期望。
好了，首先我们要知道的是，这个机器是怎么schedule的。如果没有“人”这个条件的限制，很明显就是一个greedy，先做时间最少的。但问题这里是minimize人的平均等待时间。如果还是照之前的greedy，就出问题了。题目的Case1就是例子。稍微推一下就可以发现，schedule的方法是把每个人的job都合并起来，对总时间排序，先把一个人的做完了，再做下一个人的。但一个人的工作中间的次序是任意的，谁前谁后这就是要算期望了。推出这个期望跟杨辉三角很有关系~嗯~但是还没完，如果几个人的工作总时间相同，他们之间的顺序也任意，这又是一层期望。所以要算两层，外面这层还是跟杨辉三角有关……推出公式就发现很简单了，剩下的就是仔细code了。
code的时候因为时间最大是10^9，所以int超了，fail一次……改long long，有两个小地方没改过来，又fail一次，最后过的很顺利。印象中第一次做出D1 500，再接再厉。
贴code：
#include "cmath" #include "ctime" #include "iostream" #include "string" #include "vector" #include "map" #include "cstring" #include "cstdio" #include "set" #include "algorithm" #include "queue" using namespace std; typedef long long LL; LL t[55]; bool cmp(const int i,const int j) { return t[i]<t[j]; } class BatchSystemRoulette { public: vector <double> expectedFinishTimes( vector <int> duration, vector <string> user ) { int n=duration.size(); map<string,int> m; vector<int> v[55]; int id[55]; vector<double> ret; memset(t,0,sizeof(t)); int nu=0; for(int i=0;i<n;i++) if(m.find(user[i])==m.end()) { m[user[i]]=nu++; } for(int i=0;i<n;i++) { ret.push_back(0); t[m[user[i]]]+=duration[i]; v[m[user[i]]].push_back(i); } for(int i=0;i<nu;i++) id[i]=i; sort(id,id+nu,cmp); for(int i=0;i<nu;i++) { int p=v[id[i]].size(); for(int j=0;j<p;j++) { ret[v[id[i]][j]]=duration[v[id[i]][j]]+(t[id[i]]-duration[v[id[i]][j]])/2.0; } } LL now=0,pre=t[id[0]],cnt=1; for(int i=1;i<=nu;i++) { if(i==nu||t[id[i]]!=pre) { for(int j=i-1;j>=i-cnt;j--) { int p=v[id[j]].size(); double tmp=(now*2.0+(cnt-1)*pre)/2.0; for(int k=0;k<p;k++) ret[v[id[j]][k]]+=tmp; } if(i!=nu) { now+=cnt*pre; cnt=1; pre=t[id[i]]; } } else cnt++; } return ret; } }; |