HDU 4671 Backup Plan 构造

负载是否平衡只与前两列有关,剩下的只要与前两列不重复就随便放。

第一列我们按1-n这样循环放,第二列每次找个数最少的那个服务器放。

#include <cstdio>
#include <cstring>
#include <cstdlib> using namespace std; const int MAXN = ; int N, M;
int mat[MAXN][MAXN];
int cnt[MAXN];
int ori[MAXN];
bool vis[MAXN]; void show()
{
for ( int i = ; i <= M; ++i )
{
for ( int j = ; j <= N; ++j )
{
if ( j != ) putchar(' ');
printf( "%d", mat[i][j] );
}
puts("");
}
//puts("=========");
return;
} void FangHang( int *a )
{
memset( vis, false, sizeof(vis) );
vis[ a[] ] = true;
vis[ a[] ] = true; for ( int i = ; i <= N; ++i )
{
for ( int j = ; j <= N; ++j )
if ( !vis[j] )
{
a[i] = j;
vis[j] = true;
break;
}
} return;
} int GetMin( int now )
{
int minn = << ;
int ansi;
for ( int i = ; i <= N; ++i )
{
if ( i == now ) continue;
if ( cnt[i] < minn )
{
minn = cnt[i];
ansi = i;
}
}
return ansi;
} void solved()
{
memset( cnt, , sizeof(cnt) );
for ( int i = ; i <= M; ++i )
++cnt[ mat[i][] ]; int fang = ;
int cur = ;
for ( int i = ; i <= N; ++i ) ori[i] = cnt[i];
while ( fang < M )
{
int minn;
int j = ;
while ( j <= M )
{
minn = GetMin(cur);
for ( ; j <= M; ++j )
{
if ( mat[j][] == cur && mat[j][] == - )
{
mat[j][] = minn;
++cnt[ minn ];
++fang;
break;
}
}
}
for ( int i = ; i <= N; ++i ) cnt[i] = ori[i];
++cur;
} for ( int i = ; i <= M; ++i )
{
FangHang( mat[i] );
} return;
} int main()
{
while ( scanf( "%d%d", &N, &M ) == )
{
memset( mat, -, sizeof(mat) );
int i = , j = ;
while ( i <= M )
{
mat[i][] = j;
++i, ++j;
if ( j > N ) j = ;
}
solved();
show();
}
return ;
}
上一篇:如何优化cocos2d程序的内存使用和程序大小


下一篇:Javascript玩转继承(二)