SRM481D1 500 (Greedy + Math)

一晃好多年,我终于爬回了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;
    }
};

UVA 11813 Shopping(SPFA+DP)

以前从来没真正写过SPFA,难怪training的时候做不出来了……大悲剧啊……题目的意思就是说在一个很大很大的图中从一个固定的点开始访问其中一些点并最终回到起点,求最短的路径。一些点的数量不多过10个。很容易想到状态dp。
设dp[i][j]表示的是当前在i点并且已经访问了点的状态为j。转移方程为
dp[i][j]=dp[p][k]+dis[p][i] if( (j^k)==(1<<i) && (1<<p)&(k)==true )
其中j的已访问节点数比k大1。所以做bottom-up的DP,以已访问的节点数来做。

最后最麻烦的就是SPFA的写法,参照百度百科写了一个。效率还不错。

int n,m,s,st[11];
int next[200010],ev[200010],ew[200010],nbs[100005];
int used[100005],q[100005],dis[11][100005];
void spfa(int s,int id)
{
    int head=0,tail=1,u,v,w;
    for(int i=0;i&lt;n;i++) { used[i]=q[i]=0; dis[id][i]=inf; }
    dis[id][s]=0;
    q[tail]=s; used[s]=1;
    while(head!=tail)
    {
        head=(head+1)%(n+1);
        u=q[head];
        used[u]=0;
        for(int i=nbs[u];i;i=next[i])
        {
            v=ev[i]; w=ew[i];
            if(dis[id][v]-w&gt;dis[id][u])
            {
                dis[id][v]=dis[id][u]+w;
                if(!used[v])
                {
                    tail=(tail+1)%(n+1);
                    q[tail]=v; used[v]=1;
                }
            }
        }
    }
}

要加油了。