hdu 4671 Backup Plan 结构

hdu 4671 Backup Plan 构造

真尼玛坑题，三个人读了1个多小时才懂意思。

给n个服务器，m个任务，让你给每个任务构造一个优先级队列，每个任务会优先选择排在前面的服务器为它服务。

我们要使服务器任务均匀分摊，也就是说得到最多任务的服务器的任务数不能比得到最少任务的服务器任务数多的超过1。

现在，有一台服务器会坏掉（那么需要它服务的任务就会往队列后选择下一个服务器）

很容易想到，只有第一列和第二列的数字有效，后面的可以随便排。并且很容易想到第一列的序列要这样排下来，关键是第二列应该怎么办。

这里分3种情况讨论，当n==m的时候，第二列随便选（同一行不重复就行）。

当n>m时，第二列全选n号服务器。

当n<m时，第二列选n-1个n，然后是n-1个n-1,,n-1个n-2。这样循环。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<cstring>
#include<set>
#include<utility>
using namespace std;
int a[105][105];
int vis[105][105];
int main()
{
    int st,n,m;
 //   for(n=2;n<=100;n++)   //debug用
 //   for(m=1;m<=100;m++)
    while(cin>>n>>m)
    {
        memset(vis,0,sizeof(vis));st=2;
        for(int i=1,c=0;i<=m;c++,i++)
        {
            a[i][1]=c%n+1;
            vis[i][a[i][1]]=1;
        }
        if(n>m)
        {
            st=3;
            for(int i=1;i<=m;i++) a[i][2]=n,vis[i][n]=1;
        }
        else if(n<m)
        {
            st=3;
            int t=n;
            for(int i=1;i<=m;i++)
            {
                a[i][2]=t;
                if(i%(n-1)==0) t=(t-1)?t-1:n;
                vis[i][a[i][2]]=1;
            }
        }
        for(int i=1;i<=m;i++)
            for(int j=1,t=st;j<=n;j++)
                if(!vis[i][j]) a[i][t++]=j;

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++)
                if(j==1) printf("%d",a[i][j]);
                else printf(" %d",a[i][j]);
            puts("");
        }
    }
    return 0;
}

void debug()
{
    int ans=0;
    for(int i=1;i<=n;i++){int sum[105]={0};
        for(int j=1;j<=m;j++)
            if(a[j][1]==i) sum[a[j][2]]++;
            else sum[a[j][1]]++;
    int mins=99999,maxs=-1;
    for(int kk=1;kk<=n;kk++) if(kk!=i)mins=min(mins,sum[kk]),maxs=max(maxs,sum[kk]);
    ans=max(maxs-mins,ans);
    }
    printf("%d %d %s\n",n,m,ans<=1?"yes":"no");
    if(ans>1) system("pause");
}

hdu 4671 Backup Plan 结构

相关推荐