题意: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; }