首页 > 代码库 > BZOJ 1110: [POI2007]砝码Odw
BZOJ 1110: [POI2007]砝码Odw
1110: [POI2007]砝码Odw
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 547 Solved: 296
[Submit][Status][Discuss]
Description
在byteotian公司搬家的时候,他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容
量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运,并且丢弃剩下的砝码。每个容器可以装的砝码数量有
限制,但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个砝码都有一个
特征,他们的中总有一个的重量是另外一个的整数倍,当然他们也可能相等。
Input
第一行包含两个数n和m。表示容器的数量以及砝码的数量。(1<=n, m<=100000) 第二行包含n个整数wi,表示
每个容器能够装的最大质量。(1<=wi<=1000000000) 第三行包含m个整数mj,表示每个砝码的质量。(1<=mj<=10000
00000)
Output
仅包含一个数,为能够装进容器的最多的砝码数量。
Sample Input
2 4
13 9
4 12 2 4
13 9
4 12 2 4
Sample Output
3
HINT
Source
分析
显然,因为整数倍的关系,n个砝码的重量一共只有至多logW个,大约也就是30个。我们把这些数处理出来,当作进制。这样,可以将容量表示成一个至多30位的“数”,然后贪心先满足小的砝码,如果其所在的位上是0,就尝试从高位借位,注意处理递归借位的情况即可。
代码
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7 8 #define ri register int 9 10 #define lim 100000000 11 12 char *p = new char[lim]; 13 14 template <class T> 15 void read(T &x) 16 { 17 x = 0; 18 19 while (*p < ‘0‘)++p; 20 21 while (*p >= ‘0‘) 22 x = x*10 + *p++ - ‘0‘; 23 } 24 25 #define N 100005 26 27 int n, m; 28 int w[N]; 29 int c[N]; 30 31 int bit[50], cnt[50], tot; 32 33 int cmp(const void *a, const void *b) 34 { 35 return *(int *)a - *(int *)b; 36 } 37 38 void get(int t) 39 { 40 if (t > tot)return; 41 42 if (!cnt[t + 1])get (t + 1); 43 44 if (cnt[t + 1])--cnt[t + 1], cnt[t] += bit[t + 1] / bit[t]; 45 } 46 47 signed main(void) 48 { 49 50 fread(p, 1, lim, stdin); 51 52 read(m); read(n); 53 54 for (ri i = 1; i <= m; ++i) 55 read(c[i]); 56 57 for (ri i = 1; i <= n; ++i) 58 read(w[i]); 59 60 qsort(w + 1, n, sizeof(int), cmp); 61 62 for (ri i = 1, j = 1; i <= n; i = j) 63 { 64 bit[++tot] = w[i]; 65 66 while (w[i] == w[j])++j; 67 } 68 69 bit[0] = 1; 70 71 for (ri i = 1; i <= m; ++i) 72 for (ri j = tot; c[i]; --j) 73 cnt[j] += c[i] / bit[j], c[i] %= bit[j]; 74 75 ri answer = 0; 76 77 for (ri i = 1, j = 1; i <= n; ++i) 78 { 79 if (bit[j] < w[i])++j; 80 81 if (!cnt[j])get(j); 82 83 if (cnt[j])++answer, --cnt[j]; 84 } 85 86 printf("%d\n", answer); 87 }
@Author: YouSiki
BZOJ 1110: [POI2007]砝码Odw
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。