首页 > 代码库 > HDOJ 4671 Backup Plan 构造优先队列

HDOJ 4671 Backup Plan 构造优先队列

  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <cstdio>  
  4. #include <algorithm>  
  5. #include <queue>  
  6.   
  7. using namespace std;  
  8.   
  9. int n,m;  
  10. int li[111][111];  
  11. bool have[111];  
  12.   
  13. struct DUI  
  14. {  
  15.     int x,s;  
  16.     bool operator < (const DUI xx) const  
  17.     {  
  18.         return s>xx.s;  
  19.     }  
  20. };  
  21.   
  22. int sum[111];  
  23.   
  24. int main()  
  25. {  
  26.     while(scanf("%d%d",&n,&m)!=EOF)  
  27.     {  
  28.         for(int i=1;i<=n;i++)  
  29.         {  
  30.             sum[i]=m/n+((i<=m%n)?1:0);  
  31.         }  
  32.   
  33.         for(int u=1;u<=n;u++)  
  34.         {  
  35.             priority_queue<DUI> q;  
  36.             for(int i=1;i<=n;i++)  
  37.             {  
  38.                 if(i==u) continue;  
  39.                 q.push((DUI){i,sum[i]});  
  40.             }  
  41.             for(int i=0;i<sum[u];i++)  
  42.             {  
  43.                 int pos=u+i*n;  
  44.                 DUI D=q.top(); q.pop();  
  45.   
  46.                 li[pos][1]=D.x;  
  47.   
  48.                 D.s++;  
  49.                 q.push(D);  
  50.             }  
  51.         }  
  52.   
  53.   
  54.   
  55.         for(int i=1;i<=m;i++)  
  56.         {  
  57.             int c=i;  
  58.             while(c>n) c-=n;  
  59.             li[i][0]=c;  
  60.         }  
  61.   
  62.         for(int i=1;i<=m;i++)  
  63.         {  
  64.             memset(have,false,sizeof(have));  
  65.             have[li[i][0]]=true; have[li[i][1]]=true;  
  66.             int p=1;  
  67.             for(int j=2;j<n;j++)  
  68.             {  
  69.                while(have[p]==true) p++;  
  70.                 li[i][j]=p;  
  71.                 have[p]=true;  
  72.             }  
  73.         }  
  74.   
  75.   
  76.         for(int i=1;i<=m;i++)  
  77.         {  
  78.             for(int j=0;j<n;j++)  
  79.             {  
  80.                 printf("%d%c",li[i][j],(j==n-1)?‘\n‘:‘ ‘);  
  81.             }  
  82.         }  
  83.     }  
  84.     return 0;  

HDOJ 4671 Backup Plan 构造优先队列