LA2238 Fixed Partition Memory Management

题目大意：

m(m<=10)个内存区域，n(n<=50)个程序。找出一个方案来，使得平均结束时刻尽量小。题目保证有解。

同一个程序运行在不同大小的内存区域内，其运行时间不同。（注意，这里说的大小是指整个内存区域大小，而不是说：该程序之前有程序运行，占用了一部分内存，剩下的那部分内存大小。。。。。。。）

输入：m和n，然后是m个数表示内存区域大小。再是n行，每行第1个数为情况总数k(k<=10)，然后是k对整数s1,t1,s2,t2……sk,tk，满足si<si+1表示在各个内存中的运行时间。

如果内存块总大小s不足s1，则无法在该内存块运行该程序；当si<=s<si+1时，运行时间为ti；当s>=sk时，运行时间为tk

输出：平均最小结束时间和调度方案。

（转自http://blog.csdn.net/u014679804/article/details/46725083）

题解：发现早运行的程序，对后面的结束时刻的影响是固定的，即某个内存区域倒数第p个，贡献为pT，T为程序在某个内存区域的运行时间。于是可以左边为程序，右边为每个内存区域倒数第几个运行，对应连边，边权为贡献，求最小权匹配。不难发现不会出现倒数第一匹配，倒数第二没匹配，倒数第三匹配的情况(何不匹配倒数第二呢？）

拍了很久，平均时间没有错，方案小数据看了很多组也没组

估计是SPJ没有或者不对。。。

网上的程序试了一个，都跟样例输出的一模一样，其他数据也都一模一样。。。

就当是对的吧。。OI一般也不会让输出方案反正。。

 #include <cstdio>

 #include <cstring>

 #define max(a, b) ((a) > (b) ? (a) : (b))

 template<class T>

 inline void swap(T &a, T &b)

 {

     T tmp = a;a = b;b = tmp;

 }

 inline void read(int &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '') c = ch, ch = getchar();

     while(ch <= '' && ch >= '') x = x *  + ch - '', ch = getchar();

     if(c == '-') x = -x;

 }

 const int INF = 0x3f3f3f3f;

 const int MAXN =  + ;

 const int MAXM =  + ;

 int size[MAXM * MAXN], s[MAXM * MAXN], t[MAXM * MAXN], n, m, ca;

 int g[MAXN][MAXN * MAXM], n1, n2, sla[MAXN * MAXM], pre[MAXN * MAXM], vis[MAXN * MAXM], lab1[MAXN * MAXN], lab2[MAXN * MAXM], lk1[MAXN * MAXN], lk2[MAXN * MAXM];

 void cal(int x)

 {

     memset(vis, , sizeof(vis)), memset(sla, 0x3f, sizeof(sla)), memset(pre, , sizeof(pre)), vis[] = ;

     int y;

     do

     {

         y = ;

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

         {

             if(vis[i]) continue;

             if(lab1[x] + lab2[i] - g[x][i] < sla[i]) sla[i] = lab1[x] + lab2[i] - g[x][i], pre[i] = x;

             if(sla[i] < sla[y]) y = i;

         }

         int d = sla[y];

         for(int i = ;i <= n1;++ i) if(vis[lk1[i]]) lab1[i] -= d;

         for(int i = ;i <= n2;++ i) if(vis[i]) lab2[i] += d; else sla[i] -= d;

         vis[y] = ;

     }while(x = lk2[y]);

     for(;y;swap(y, lk1[lk2[y] = pre[y]]));

 }

 double KM()

 {

     for(int i = ;i <= n1;++ i) cal(i);

     int ans = ;

     for(int i = ;i <= n1;++ i) ans += g[i][lk1[i]];

     return (double)-ans;

 }

 int tag[MAXN], from[MAXN], to[MAXN], stack[MAXN], tot;

 int main()

 {

     while(scanf("%d %d\n", &m, &n) != EOF && n && m)

     {

         if(ca) putchar('\n');

         memset(from, , sizeof(from)), memset(tag, , sizeof(tag)), memset(to, , sizeof(to)), memset(stack, , sizeof(stack)), n1 = n, n2 = n * m, ++ ca, memset(lab1, -0x3f, sizeof(lab1)), memset(lk1, , sizeof(lk1)), memset(lk2, , sizeof(lk2)), memset(g, -0x3f, sizeof(g)), memset(lab2, , sizeof(lab2));

         for(int i = ;i <= m;++ i) read(size[i]);

         for(int i = ;i <= n;++ i)//考虑每个程序

         {

             int k;read(k);

             for(int j = ;j <= k;++ j) read(s[j]), read(t[j]);

             s[k + ] = INF;

             for(int j = ;j <= m;++ j)//在区域j中

                 for(int l = ;l <= k;++ l)

                     if(s[l] <= size[j] && size[j] < s[l + ])//运行时间为t[l]

                         for(int p = ;p <= n;++ p) //倒数第p个运行

                             g[i][(j - ) * n + p] = - p * t[l], lab1[i] = max(lab1[i], - p * t[l]);

         }

         printf("Case %d\nAverage turnaround time = %.2lf\n", ca, KM() / (double)n);

         for(int i = ;i <= n;++ i) tag[i] = (lk1[i] - ) / n + ;

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

         {

             tot = ;int sum = ;

             for(int j = ;j <= n;++ j) if(tag[j] == i) stack[++ tot] = j;

             for(;tot;-- tot)

                 from[stack[tot]] = sum, to[stack[tot]] = sum = sum + (-g[stack[tot]][lk1[stack[tot]]] / ((lk1[stack[tot]] - ) % n + ));

         }

         for(int i = ;i <= n;++ i) printf("Program %d runs in region %d from %d to %d\n", i, tag[i], from[i], to[i]);

     }

     return ;

 }

LA2238

巴特西

LA2238 Fixed Partition Memory Management

最新文章

热门文章