首页 > 代码库 > codeforces 507B. Painting Pebbles 解题报告
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排序比较第一个和最后一个元素之差即可。最后就输出结果了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 using namespace std; 8 9 const int maxn = 100 + 5;10 vector<int> v[maxn], ans[maxn];11 vector<int>:: iterator vp1, vp2;12 int a[maxn];13 int cnt[maxn];14 15 int main()16 {17 #ifndef ONLINE_JUDGE18 freopen("in.txt", "r", stdin);19 #endif // ONLINE_JUDGE20 21 int n, k;22 while (scanf("%d%d", &n, &k) != EOF) {23 for (int j = 0; j <= maxn; j++) {24 ans[j].clear();25 v[j].clear();26 }27 28 for (int j = 0; j < n; j++) {29 scanf("%d", &a[j]);30 memset(cnt, 0, sizeof(cnt));31 for (int i = 0; i < a[j]; i++) {32 int tmp = ((i+1) % k ? (i+1) % k : k);33 cnt[tmp]++;34 } // 填色35 for (int i = 1; i <= k; i++) {36 ans[i-1].push_back(cnt[i]);37 v[i-1].push_back(cnt[i]);38 }39 }40 bool flag = true;41 for (int i = 0; i < k; i++) {42 sort(v[i].begin(), v[i].end());43 vp1 = v[i].begin();44 vp2 = v[i].end()-1;45 if (*vp2 - *vp1 > 1) {46 flag = false;47 break;48 }49 }50 if (!flag)51 printf("NO\n");52 else {53 printf("YES\n");54 for (int i = 0; i < n; i++) {55 for (int j = 0; j < a[i]; j++) {56 printf("%d ", (j+1) % k ? (j+1) % k : k);57 }58 printf("\n");59 }60 }61 }62 return 0;63 }
codeforces 507B. Painting Pebbles 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。