PAT《数据结构学习与实验指导》实验项目集 2-09 2-10 2-11 2-12 2-13

 1 #include<cstdio>
 2 #include<set>
 3 #include<vector>
 4 using namespace std;
 5 
 6 int findMatchBox(int tsize, vector<int> &box)
 7 {
 8     for(int i = 0; i < box.size(); i++)
 9         if(box[i] >= tsize)return i;
10     return -1;
11 }
12 
13 int main()
14 {
15     int N;
16     scanf("%d", &N);
17     vector<int> box;//box[i]为箱子i的剩余容量
18     for(int i = 0; i < N; i++)
19     {
20         int tsize;
21         scanf("%d", &tsize);
22         int boxindex = findMatchBox(tsize, box);
23         if(boxindex != -1)
24         {
25             box[boxindex] -= tsize;
26             printf("%d %d
", tsize, boxindex+1);
27         }
28         else
29         {
30             box.push_back(100 - tsize);
31             printf("%d %d
", tsize, box.size());
32         }
33     }
34     printf("%d
", box.size());
35     return 0;
36 }

View Code

pat 2-10 海盗分赃

这是一道智力推理题，假设有p个海盗，第一个海盗考虑分配方案时，他是建立在假设自己死后第二个海盗的分配方案基础上的，在题目的三个假设的基础上，他只要按如下方法分配即可：

给第二个人0个钻石，因为给不给第二个人钻石，他都会投反对票，因为他知道把第二个人投死后，让他来分配自己利益最大。本文地址
对于其他人，在第二个海盗的分配方案基础上，给分配到0个钻石的人每人一个钻石，给分配到1个钻石的人中选择序号最小的给他2个钻石，其余的人都给0个钻石，这样的话，分到钻石的人都会觉得自己投赞成票比投反对票有利
当总人数是3时，特别考虑：给第二个人1颗钻石，第三个人0颗钻石。因为轮到第二个人分配时，第三个人肯定投反对票，这样他就会得到所有钻石，所以只要给第二个人1颗钻石，他就肯定会投赞成票

上面的问题可以很简单的用递归来解决，如果只需要求第一个人的钻石数目，从以下的分配方案中可以发现有更简单的规律：第一个人的钻石数目是：D - P/2 - 1（其中D是钻石总数目，除法向下取整，P = 3时特别考虑）

P=3: D-1 1 0
P=4： D-3 0 2 1
P=5: D-3 0 1 0 2
P=6: D-4 0 1 2 1 0
P=7: D-4 0 1 2 0 0 1

海盗分赃的详细分析可参考：here

该题的通过代码：

1 int main()
2 {
3     int D,P;
4     scanf("%d%d", &D, &P);
5     if(P == 3)printf("%d", D-1);
6     else printf("%d",D-(P/2+1));
7     return 0;
8 }

View Code

以下代码根据上面分析的递归算法可以打印出每个人分配到的钻石数目：

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 
 5 void haidao(int diamondNum, int personNum, int scheme[])
 6 {
 7     if(diamondNum < personNum)return;
 8     if(personNum == 3)
 9     {
10         scheme[0] = diamondNum - 1;
11         scheme[1] = 1;
12         scheme[2] = 0;
13     }
14     else
15     {
16         int nextScheme[personNum];
17         haidao(diamondNum, personNum-1, nextScheme);
18         scheme[1] = 0;
19         bool flag = false;
20         int giveOut = 0;
21         for(int i = 2; i < personNum; i++)
22         {
23             if(nextScheme[i-1] == 0)
24             {
25                 scheme[i] = 1;
26                 giveOut++;
27             }
28             else if(nextScheme[i-1] == 1 && flag == false)
29             {
30                 scheme[i] = 2;
31                 flag = true;
32                 giveOut += 2;
33             }
34             else scheme[i] = 0;
35         }
36         scheme[0] = diamondNum - giveOut;
37     }
38 }
39 
40 int main()
41 {
42     int D,P;
43     scanf("%d%d", &D, &P);
44     int scheme[P];
45     haidao(D, P, scheme);
46     for(int i = 0; i < P; i++)
47         printf("%d", scheme[0]);
48 }

View Code

pat 2-11两个有序链表序列的合并

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     vector<int> list1,list2;
 8     int tmp;
 9     do
10     {
11         scanf("%d", &tmp);
12         list1.push_back(tmp);
13     }while(tmp != -1);
14     do
15     {
16         scanf("%d", &tmp);
17         list2.push_back(tmp);
18     }while(tmp != -1);
19     if(list1.size() == 1 && list2.size() == 1)
20         {printf("NULL
"); return 0;}
21     int i = 0, j = 0;
22     while(list1[i] != -1 && list2[j] != -1)
23     {
24         if(list1[i] <= list2[j])
25             printf("%d ", list1[i++]);
26         else printf("%d ", list2[j++]);
27     }
28     if(list1[i] == -1)
29     {
30         for(; j <= list2.size()-3; j++)
31             printf("%d ", list2[j]);
32         printf("%d
", list2[j]);
33     }
34     if(list2[j] == -1)
35     {
36         for(; i <= list1.size()-3; i++)
37             printf("%d ", list1[i]);
38         printf("%d
", list1[i]);
39     }
40 }

View Code

pat 2-12 两个有序链表序列的交集

 1 include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 int main()
 5 {
 6     vector<int> list1,list2;
 7     int tmp;
 8     do
 9     {
10         scanf("%d", &tmp);
11         list1.push_back(tmp);
12     }while(tmp != -1);
13     do
14     {
15         scanf("%d", &tmp);
16         list2.push_back(tmp);
17     }while(tmp != -1);
18     int i = 0, j = 0;
19     bool isFirst = true;
20     while(list1[i] != -1 && list2[j] != -1)
21     {
22         if(list1[i] == list2[j])
23         {
24             if(isFirst == false)
25                 printf(" ");
26             isFirst = false;
27             printf("%d", list1[i]);
28             i++; j++;
29         }
30         else if(list1[i] < list2[j])i++;
31         else j++;
32     }
33     if(isFirst == true)printf("NULL");
34     return 0;
35 }

View Code

pat 2-13 两个有序序列的中位数

 1 #include<cstdio>
 2 
 3 int main()
 4 {
 5     int n;
 6     scanf("%d", &n);
 7     int arr1[n], arr2[n];
 8     for(int i = 0; i < n; i++)
 9         scanf("%d", &arr1[i]);
10     for(int i = 0; i < n; i++)
11         scanf("%d", &arr2[i]);
12     int k = 1, i = 0, j = 0;
13     while(1)
14     {
15         if(arr1[i] < arr2[j])
16         {
17             if(k == n)
18                 {printf("%d", arr1[i]); return 0;}
19             i++;
20         }
21         else
22         {
23             if(k == n)
24                 {printf("%d", arr2[j]); return 0;}
25             j++;
26         }
27         k++;
28     }
29     return 0;
30 }

View Code