题目来源：POJ3040

分析

题目大意：

给定N(<=20)种钞票,第i种面值为a[i],数量为b[i]

每周要给奶牛C(<=10^8)元的工资，求最多可以给几周。

注意：

1）给的工资每周不少于C元。

2）任意i,j 若a[i]<a[j] 则 a[j]为a[i]的倍数

肯定是贪心，但问题是怎么贪

解法

根据网上的题解和大表的结论

关键在于注意2，大的数一定是小的数的倍数。

于是大的数是可以由前面小数凑成的，性质其实一样，因此早取不会比晚取劣。

那么就是每次把能放的下的大数放进去，然后用小的补齐。

对于每一次取数 (取出的和大于等于C，就是付一次工资)

用d[]数组表示这次取数中，第k个数拿了d[k]个

rest = C 表示至少还要多少钱

1)第一轮从大到小取，对于第k个数，取到饱和，rest>=0

那么从大到小取 

1
2
3
4
5
if (rest div a[k])<=b[k] then d[k] = rest div a[k] 

                                else d[k] = b[k]

rest = rest - a[k]*d[k]

2)第二轮从小到大取，对于第k个数，取到超过所需为止，rest<=0

若 第k个数能够把剩下的工资补完,则 d[k] = rest div a[k](除不尽要+1) rest = 0

若 第k….不能…………….,则 d[k] = b[k] rest = rest - b[k]*a[k]

这样得到了d[]数组

如果一次一次地做，肯定会超时。。

这样对于d[]数组，相当于一种给工资的方案，我们就可以统计这个方案最多可以用几次，然后再换一个方案。

对于第k个数，d[]方案可以使用的次数为 time[k] = b[k] div d[k]

找出最小的time[k]，就是这个方案可使用的次数

然后更新b[] ，b[k] = b[k] - time[k]*d[k]

重复做，知道再也不能找出一种方案为止

优化

以上

详解

细节

一定要注意两轮取数的差别，第一次的约束条件是rest>=0 第二次的终止条件是rest<=0

源程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
Program Lwx;
Var 	n, c:longint;
    	a, b, d:array[1..20] of longint;
    	i, j, k, l, x, y, z, use,ans:longint;

Begin
  	assign(input, 'test.in'); reset(input);
  	readln(n, c);
  	for i := 1 to n do read(a[i], b[i]);
  	close(input);
  	for i := 1 to n-1 do
   	for j := i+1 to n do
   	if a[i] < a[j] then
   	begin
     		x := a[i]; a[i] :=a [j]; a[j] := x;
     		x := b[i]; b[i] := b[j]; b[j] := x;
   	end;

  	ans := 0;
  	i := 1;

  	while true do
  	begin
    		if i > n then break;
    		if b[i] = 0 then
    		begin
      			inc(i);
      			continue;
    		end;

    		if a[i] >= c then
    		begin
      			ans := ans + b[i];
      			b[i] := 0;
     			inc(i);
      			continue;
    		end;

    		x := c;
    		for k := i to n do
    		begin
      			d[k] := 0;
      			z := x div a[k];
      			if z <= b[k] then d[k] := z else
                        d[k] := b[k];
      			x := x - a[k]*d[k];
    		end;

    		y := n;
    		while x > 0 do
   		begin
      			if y < 1 then break;
      			if b[y] = d[y] then
      			begin
        			dec(y);
        			continue;
      			end;
      		z := x div a[y] + ord(x mod a[y] <> 0);
      		if z + d[y] <= b[y] then
      		begin
        		x := 0;
        		d[y]:=d[y]+z;
      			end else
      			begin
        			x := x - a[y]*(b[y] - d[y]);
        			d[y] := b[y];
      			end;
    		end;
    		if x = 0 then
    		begin
      			z := maxlongint;
      			for k := i to n do
      			if d[k] > 0 then
      			if b[k] div d[k] < z then z := b[k] div d[k];
      			if z < maxlongint then
      			begin
        			ans := ans+z;
        			for k := i to n do b[k] := b[k] - d[k]*z;
      			end;
    		end else break;
  	end;
  	write(ans);
End.