1262 邮费规划 题解

红小豆

思维硬控神器，您值得拥有题目传送门
这里为箱子编号 s1 - s6
s6:
一个就把箱子塞满了
s5:
放完一个还能放11个s1
s4:
放了一个还能放20个s1或者5个s2
剩下的空间先放s2，之后再放s1
s3:
放4个就能凑满一个包裹
剩下的要分开想：
剩下3个，还能放1个s2和5个s1，或者9个s1
剩下2个，还能放3个s2和6个s1，或者18个s1
剩下1个，还能放5个s2和7个s1，或者27个s1
剩下0个，不用开箱子
s2:



18个能铺满箱子。有剩余的话再新开一个箱子（空余的铺s1）
s1:
36个就能铺满，不够就新开个箱子吧

1. #include <iostream>
   
2. using namespace std;
   
3. int work(int*,int);
   
4. int main(){
   
5.         int a[10];
   
6.         cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6];
   
7.         while (a[1] != 0 || a[2] != 0 || a[3] != 0 || a[4] != 0 || a[5] != 0 || a[6] != 0){
   
8.                 cout << work(a,0) << '\n';
   
9.                 cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6];
   
10.         }
    
11. return 0;
    
12. }
    
13. int work(int a[],int box = 0){
    
14.         //放6，无剩余
    
15.         box += a[6];
    
16.         //放5，剩下a[5]*11个大小为1的空位
    
17.         box += a[5];
    
18.         if (a[5] * 11 <= a[1]) a[1] -= a[5] * 11;
    
19.         else a[1] = 0;
    
20.         //放4，剩下a[4]*20个大小为1的空位或a[4]*5个大小为2的空位
    
21.         box += a[4];
    
22.         int empty_4 = a[4] * 20;
    
23.         if (empty_4 / 4 <= a[2]) a[2] -= empty_4 / 4;
    
24.         else{
    
25.                 empty_4 -= a[2] * 4;
    
26.                 a[2] = 0;
    
27.                 if (empty_4 < a[1]) a[1] -= empty_4;
    
28.                 else a[1] = 0;
    
29.         }
    
30.         //放3，凑齐4个的话可以拼成一个大的，其余的先考虑用2，在考虑用1
    
31.         box += (a[3] + 3) / 4;
    
32.         a[3] %= 4;
    
33.         if (a[3] == 3){//剩余3块
    
34.                 if (a[2] >= 1){
    
35.                         a[2]--;
    
36.                         if (a[1] >= 5) a[1] -= 5;
    
37.                         else a[1] = 0;
    
38.                 }else{
    
39.                         if (a[1] >= 9) a[1] -= 9;
    
40.                         else a[1] = 0;
    
41.                 }
    
42.         }else if (a[3] == 2){//剩余2块
    
43.                 if (a[2] >= 3){
    
44.                         a[2] -= 3;
    
45.                         if (a[1] >= 6) a[1] -= 6;
    
46.                         else a[1] = 0;
    
47.                 }else{
    
48.                         int empty_3 = 18 - a[2] * 4;
    
49.                         a[2] = 0;
    
50.                         if (a[1] >= empty_3) a[1] -= empty_3;
    
51.                         else a[1] = 0;
    
52.                 }
    
53.         }else if (a[3] == 1){//剩余一块（0块不用新开个箱子）
    
54.                 if (a[2] >= 5){
    
55.                         a[2] -= 5;
    
56.                         if (a[1] >= 7) a[1] -= 7;
    
57.                         else a[1] = 0;
    
58.                 }else{
    
59.                         int empty_3 = 27 - a[2] * 4;
    
60.                         a[2] = 0;
    
61.                         if (a[1] >= empty_3) a[1] -= empty_3;
    
62.                         else a[1] = 0;
    
63.                 }
    
64.         }
    
65.         //9个2块的拼成一个大正方形
    
66.         box += (a[2] + 8) / 9;
    
67.         a[2] %= 9;
    
68.         if (a[2] != 0){
    
69.                 int size_2 = 36 - a[2] * 2;
    
70.                 if (size_2 <= a[1]) a[1] -= size_2;
    
71.                 else a[1] = 0;
    
72.         }
    
73.         //单独考虑1
    
74.         box += (35 + a[1]) / 36;
    
75.         return box;
    
76. }

复制代码