codeforces 507B. Painting Pebbles 解题报告

题目链接:http://codeforces.com/problemset/problem/509/B

题目意思:有 n 个piles,第 i 个 piles有 ai 个pebbles,用 k 种颜色去填充所有存在的pebbles,使得任意两个piles,用颜色c填充的pebbles数量之差 <= 1。如果不填充某种颜色,就默认数量为0。

  这样说还是比较难理解吧~~~以第三组数据为例:

5 4
3 2 4 3 5
YES
1 2 3
1 3
1 2 3 4
1 3 4
1 1 2 3 4

第2个 pile 和 第5个 pile 的比较结果如下:

cha[1] = 1 (第2个pile用颜色1填充的数量是1,第5个pile为2)

  cha[2] = 1 (第2个pile用颜色2填充的数量是0,第5个pile为1)

  cha[3] = 0;  cha[4] = 1

要想差尽可能少,就要使得颜色尽量分散。就是说,假如有个 pile 的 pebble 数目为5,可选颜色有4种,这样填就是尽量分散: 1 2 3 4 1。每个pile都这样处理,然后比较两两pile以颜色c填充的数量是否大于1,这样用vector排序比较第一个和最后一个元素之差即可。最后就输出结果了。

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; const int maxn = + ;
vector<int> v[maxn], ans[maxn];
vector<int>:: iterator vp1, vp2;
int a[maxn];
int cnt[maxn]; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE int n, k;
while (scanf("%d%d", &n, &k) != EOF) {
for (int j = ; j <= maxn; j++) {
ans[j].clear();
v[j].clear();
} for (int j = ; j < n; j++) {
scanf("%d", &a[j]);
memset(cnt, , sizeof(cnt));
for (int i = ; i < a[j]; i++) {
int tmp = ((i+) % k ? (i+) % k : k);
cnt[tmp]++;
} // 填色
for (int i = ; i <= k; i++) {
ans[i-].push_back(cnt[i]);
v[i-].push_back(cnt[i]);
}
}
bool flag = true;
for (int i = ; i < k; i++) {
sort(v[i].begin(), v[i].end());
vp1 = v[i].begin();
vp2 = v[i].end()-;
if (*vp2 - *vp1 > ) {
flag = false;
break;
}
}
if (!flag)
printf("NO\n");
else {
printf("YES\n");
for (int i = ; i < n; i++) {
for (int j = ; j < a[i]; j++) {
printf("%d ", (j+) % k ? (j+) % k : k);
}
printf("\n");
}
}
}
return ;
}
上一篇:B. Painting Pebbles


下一篇:codeforces 509 B题 Painting Pebbles