题意:n*m的格子,有的格子上面有米, k只鸡,要使每个鸡分到的米最大相差最小,还要使每个鸡分到的区域连续,要求输出一种可行方案。
差距肯定使最大也就是1 了,设总米数为sum,每个鸡要不然就是 sum / k,要不然就是 (sum / k ) + 1,(设想如果出现每个都是(sum / k ) + 1),,,那这是不可能的啊,商肯定要增加1)
知道每个鸡应该分多少米之后就是如何构造的问题,,学到了一种很巧妙的构造方法。。蛇形(S形)构造,保证连通而且真的很好写。。
int n, m, k;
char mp[110][110];
char tr(int x)
{
if (x <= 26) return x + 'a' - 1;
if (x <= 52) return x + 'A' - 27;
return x - 53 + '0';
}
int main()
{
fast;
int t;cin>>t;
while (t--)
{
cin>>n>>m>>k;
int sum = 0;
for (int i = 0; i < n; i++)
{
scanf("%s", mp[i]);
for (int j = 0; j <=m;j++) if (mp[i][j] == 'R') ++sum;
}
int av = sum / k;
int num = sum - av * k;//多少鸡应该多一个米
int cnt=0;//当前鸡有多少米
int id=1;//编号
for (int x = 0; x < n; x++)
{
if(x%2==0)
{
for (int y = 0; y < m; y++)
{
cout<<tr(id);
if(mp[x][y]=='R') ++cnt;
if(cnt==av+1&&num>0&&id<k) --num,cnt=0,++id;
else if(cnt==av&&num==0&&id<k) cnt=0,++id;
}
}
else
{
string w;
for(int y=m-1;y>=0;--y)
{
w.push_back(tr(id));
if(mp[x][y]=='R') ++cnt;
if(cnt==av+1&&num>0&&id<k) --num,cnt=0,++id;
else if(cnt==av&&num==0&&id<k) cnt=0,++id;
}
reverse(w.begin(), w.end());
cout<<w;
}
cout<<'\n';
}
}
return 0;
}

京公网安备 11010502036488号