首页 > > 程序设计 > C/C++ >

结题报告

2020-02-03 16:00:39来源：博客园阅读 ()

结题报告

题目：点此

优先队列思路：{

先读入，读入的数据放入优先队列，再循环：{

取出两个数，把这两堆果子合并，记录耗费体力并保存合并后果子的重量。

}

输出。

}

暴力思路：{

与优先队列没什么区别，只是放入优先队列改成了用插入排序或冒泡排序确定放的位置。

}

犯的错误：{

1.函数内要改变的值做参数时应用指针类型。

2.vector::insert的第一个参数应为iterator，而不是int。

3.插入排序读入循环没考虑i=0的情况。

4.优先队列主循环结束条件应是队列只有一个数，而不是队列空。

}（由于这次错误大多没被记载，犯的错误不止这些，敬请谅解。）

收获：{

1.函数内要改变的值做参数时应用指针类型。

2.vector::insert的第一个参数应为iterator，而不是int。

3.要考虑周全，不要想当然。

}

暴力代码（50分，冒泡排序）：

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 int buble_insert_sort(int insertx,vector<int> *insert_x){
 5     insert_x->insert(insert_x->begin(),insertx);
 6     for(int i=0;i<insert_x->size()-1;i++){
 7         if(insert_x->operator[](i)>insert_x->operator[](i+1)){
 8             insert_x->operator[](i)^=insert_x->operator[](i+1);
 9             insert_x->operator[](i+1)^=insert_x->operator[](i);
10             insert_x->operator[](i)^=insert_x->operator[](i+1);
11         }
12     }
13 }
14 vector <int> x;
15 int main(){
16     int n,sum=0;
17     cin >> n;
18     for(int i=0;i<n;i++){
19         int data;
20         cin >> data;
21         buble_insert_sort(data,&x);
22     }
23     for(int i=0;i<n-1;i++){
24         int a=x.front();
25         x.erase(x.begin(),x.begin()+1);
26         int b=x.front();
27         x.erase(x.begin(),x.begin()+1);
28         sum+=(a+b);
29         buble_insert_sort(a+b,&x);
30     }
31     cout << sum;
32     return 0;
33 }

暴力代码（10分，剩下的未知原因WA，插入排序）：

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 int insert_insert_sort(int insertx,vector<int> *insert_x){
 5     for(int i=0;i>insert_x->size();i++){
 6         if(insert_x->operator[](i)>insertx){
 7             insert_x->insert(insert_x->begin()+i,insertx);
 8             return 0;
 9         }
10     }
11     insert_x->insert(insert_x->end(),insertx);
12     return 0;
13 }
14 vector <int> x;
15 int main(){
16     int n,sum=0;
17     cin >> n;
18     for(int i=0;i<n;i++){
19         int data;
20         cin >> data;
21         if(i==0){
22             x.push_back(data);
23             continue;
24         }
25         insert_insert_sort(data,&x);
26     }
27     for(int i=0;i<n-1;i++){
28         int a=x.front();
29         x.erase(x.begin(),x.begin()+1);
30         int b=x.front();
31         x.erase(x.begin(),x.begin()+1);
32         sum+=(a+b);
33         insert_insert_sort(a+b,&x);
34     }
35     cout << sum;
36     return 0;
37 }

优先队列（AC）：

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 priority_queue <int,vector<int>,greater<int> > x;
 5 int main(){
 6     int n;
 7     cin >> n;
 8     int sum=0;
 9     for(int i=0;i<n;i++){
10         int data;
11         cin >> data;
12         x.push(data);
13     }
14     while(x.size()>1){
15         int a=x.top();
16         sum+=a;
17         x.pop();
18         int b=x.top();
19         sum+=b;
20         x.pop();
21         x.push(a+b);
22     }
23     cout << sum;
24     return 0;
25 }