求助帖，求问stanford公开课Algorithms: Design and Analysis, Part I (Week 1)的问题

题目：
Question 1

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.

求问第一周编程题，第一次使用vector写代码。为什么算出来的结果和用动态数组写的代码算出来的不一样 使用vector写的程序代码,算出来是2584786980.

• #include<iostream>
• #include<vector>
• #include<fstream>
• using namespace std;
• long long countInversion(vector<int> & vec)
• {
•         int n = vec.size();
•         if (n != 1)
•         {
•                 vector<int> b, c;
•                 for (int i = 0; i < n / 2; i++)
•                 {
•                         b.push_back(vec[i]);
•                 }
•                 for (int i = 0; i < n - n / 2; i++)
•                 {
•                         c.push_back(vec[n / 2 + i]);
•                 }
•                 long long num1 = countInversion(b);
•                 long long num2 = countInversion(c);
•                 long long num3 = 0;
•                 vec.clear();
•                 int i = 0, j = 0;
•                 for (int k = 0; k < n; k++)
•                 {
•                         if (i < n / 2 && j<n - n / 2)
•                         {
•                                 if (b[i] <= c[j])
•                                 {
•                                         vec.push_back(b[i]);
•                                         i++;
•                                 }
•                                 else if (b[i]>c[j])
•                                 {
•                                         vec.push_back(c[i]);
•                                         num3 = num3 + n / 2 - i;
•                                         j++;
•                                 }
•                         }
•                         else if (i >= n / 2)
•                         {
•                                 vec.push_back(c[j]);
•                                 j++;
•                         }
•                         else if (j >= n - n / 2)
•                         {
•                                 vec.push_back(b[i]);
•                                 i++;
•                         }
•                 }
•                 long long ans = num1 + num2 + num3;
•                 return ans;
•         }
•         else if (n == 1)
•                 return 0;
• }
• int main(void)
• {
•         vector<int> a;
•         int temp;
•         ifstream fin("D:\\IntegerArray.txt");
•         if (!fin)
•         {
•                 cout << "can't open file";
•                 return 1;
•         }
•         for (int i = 0; i < 100000; i++)
•         {
•                 fin >> temp;
•                 a.push_back(temp);
•         }
•         long long ans = countInversion(a);
•         cout << a.size()<<'\t'<<ans;
•         getchar();
•         getchar();
•         return 0;
• }
  

[color=rgb(73, 123, 137) !important]复制代码
使用动态数组算出来的结果是2407905288

• #include<iostream>
• #include<fstream>
• using namespace std;
• long long inven(int a[],int n)
• {
•         if (n != 1)
•         {
•                 int *b=new int[n/2];
•                 int *c=new int[n-n/2];
•                 for (int i = 0; i < n / 2; i++)
•                 {
•                         b[i] = a[i];
•                 }
•                 for (int i = 0; i < n - n / 2; i++)
•                 {
•                         c[i] = a[n / 2 + i];
•                 }
•                 long long num1 = inven(b,n/2);
•                 long long num2 = inven(c,n-n/2);
•                 long long num3 = 0;
•                 int i = 0, j = 0;
•                 for (int k = 0; k < n; k++)
•                 {
•                         if (i < n / 2 && j<n-n/2)
•                         {
•                                 if (b[i] <= c[j])
•                                 {
•                                         a[k] = b[i];
•                                         i++;
•                                 }
•                                 else if (b[i]>c[j])
•                                 {
•                                         a[k] = c[j];
•                                         num3 = num3 + n / 2 - i;
•                                         j++;
•                                 }
•                         }
•                         else if (i >= n / 2)
•                         {
•                                 a[k] = c[j];
•                                 j++;
•                         }
•                         else if (j >= n - n / 2)
•                         {
•                                 a[k] = b[i];
•                                 i++;
•                         }
•                 }
•                 delete b;
•                 delete c;
•                 long long ans = num1 + num2 + num3;
•                 return ans;
•         }
•         else if (n == 1)
•                 return 0;
• }
• int main(void)
• {
•         ifstream fin("D:\\IntegerArray.txt");
•         if (!fin)
•         {
•                 cout << "can't open file";
•                 return 1;
•         }
•         int a[100000];
•         for (int i = 0; i < 100000; i++)
•         {
•                 fin >> a[i];
•         }
•         long long ans = inven(a,100000);
•         cout << ans;
•         getchar();
•         getchar();
•         return 0;
• }
  

[color=rgb(73, 123, 137) !important]复制代码
蟹蟹各位啦

重新贴一下代码
vector数据结构写的：

1. #include<iostream>
   
2. #include<vector>
   
3. #include<fstream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. long long countInversion(vector<int> & vec)
   
8. {
   
9.         int n = vec.size();
   
10.         if (n != 1)
    
11.         {
    
12.                 vector<int> b, c;
    
13.                 for (int i = 0; i < n / 2; i++)
    
14.                 {
    
15.                         b.push_back(vec[i]);
    
16.                 }
    
17.                 for (int i = 0; i < n - n / 2; i++)
    
18.                 {
    
19.                         c.push_back(vec[n / 2 + i]);
    
20.                 }
    
21.                 long long num1 = countInversion(b);
    
22.                 long long num2 = countInversion(c);
    
23.                 long long num3 = 0;
    
24.                 vec.clear();
    
25.                 int i = 0, j = 0;
    
26.                 for (int k = 0; k < n; k++)
    
27.                 {
    
28.                         if (i < n / 2 && j<n - n / 2)
    
29.                         {
    
30.                                 if (b[i] <= c[j])
    
31.                                 {
    
32.                                         vec.push_back(b[i]);
    
33.                                         i++;
    
34.                                 }
    
35.                                 else if (b[i]>c[j])
    
36.                                 {
    
37.                                         vec.push_back(c[i]);
    
38.                                         num3 = num3 + n / 2 - i;
    
39.                                         j++;
    
40.                                 }
    
41.                         }
    
42.                         else if (i >= n / 2)
    
43.                         {
    
44.                                 vec.push_back(c[j]);
    
45.                                 j++;
    
46.                         }
    
47.                         else if (j >= n - n / 2)
    
48.                         {
    
49.                                 vec.push_back(b[i]);
    
50.                                 i++;
    
51.                         }
    
52.                 }
    
53.                 long long ans = num1 + num2 + num3;
    
54.                 return ans;
    
55.         }
    
56.         else if (n == 1)
    
57.                 return 0;
    
58. }
    
59. 
    . From 1point 3acres bbs
60. 
    
61. int main(void)
    
62. {
    
63.         vector<int> a;
    
64.         int temp;
    
65.         ifstream fin("D:\\IntegerArray.txt");
    
66.         if (!fin)
    
67.         {
    
68.                 cout << "can't open file";
    
69.                 return 1;
    
70.         }
    
71.         for (int i = 0; i < 100000; i++)
    
72.         {
    
73.                 fin >> temp;
    
74.                 a.push_back(temp);
    
75.         }
    
76.         long long ans = countInversion(a);
    
77.         cout << a.size()<<'\t'<<ans;
    
78.         getchar();
    
79.         getchar();
    
80.         return 0;
    
81. }

复制代码

动态数组写的代码：

1. #include<iostream>
   
2. #include<fstream>
   
3. using namespace std;
   
4. 
   
5. long long inven(int a[],int n)
   
6. {
   
7.         if (n != 1)
   
8.         {
   
9.                 int *b=new int[n/2];
   
10.                 int *c=new int[n-n/2];
    
11.                 for (int i = 0; i < n / 2; i++)
    
12.                 {
    
13.                         b[i] = a[i];
    
14.                 }
    
15.                 for (int i = 0; i < n - n / 2; i++)
    
16.                 {
    
17.                         c[i] = a[n / 2 + i];
    
18.                 }
    
19.                 long long num1 = inven(b,n/2);
    
20.                 long long num2 = inven(c,n-n/2);
    
21.                 long long num3 = 0;
    
22.                 int i = 0, j = 0;
    
23.                 for (int k = 0; k < n; k++)
    
24.                 {
    
25.                         if (i < n / 2 && j<n-n/2)
    
26.                         {
    
27.                                 if (b[i] <= c[j])
    
28.                                 {
    
29.                                         a[k] = b[i];
    
30.                                         i++;
    
31.                                 }
    
32.                                 else if (b[i]>c[j])
    
33.                                 {
    
34.                                         a[k] = c[j];
    
35.                                         num3 = num3 + n / 2 - i;
    
36.                                         j++;
    
37.                                 }
    
38.                         }
    
39.                         else if (i >= n / 2)
    
40.                         {
    
41.                                 a[k] = c[j];
    
42.                                 j++;
    
43.                         }
    
44.                         else if (j >= n - n / 2)
    
45.                         {
    
46.                                 a[k] = b[i];
    
47.                                 i++;
    
48.                         }
    
49.                 }
    
50.                 delete b;
    
51.                 delete c;
    
52.                 long long ans = num1 + num2 + num3;
    
53.                 return ans;
    
54.         }
    
55.         else if (n == 1)
    
56.                 return 0;
    
57. }
    
58. 
    
59. int main(void)
    
60. {
    
61.         ifstream fin("D:\\IntegerArray.txt");
    
62.         if (!fin)
    
63.         {
    
64.                 cout << "can't open file";
    
65.                 return 1;
    
66.         }
    
67.         int a[100000];
    
68.         for (int i = 0; i < 100000; i++)
    
69.         {
    
70.                 fin >> a[i];
    
71.         }
    
72.         long long ans = inven(a,100000);
    
73.         cout << ans;
    
74.         getchar();
    
75.         getchar();
    
76.         return 0;
    
77. }

复制代码

蟹蟹大家啦！！！