favour @ 2019-08-20 15:52:33
如题,不知道哪错了
using namespace std;
#include <iostream>
#include <vector>
struct num{
int n;
int count;
num(int x):n(x),count(0){
}
};
void merge(std:: vector<num>&vec1,std:: vector<num>vec2,std:: vector<num>&vec){
int i(0),j(0);
for(;i<vec1.size(),j<vec2.size();){
if(vec1[i].n<=vec2[j].n){
vec1[i].count+=j;
vec.push_back(vec1[i]);
i++;
}
else{
vec.push_back(vec2[j]);
j++;
}
}
if(i<vec1.size()){
while(i<vec1.size()){
vec1[i].count+=vec2.size();
vec.push_back(vec1[i]);
i++;
}
}
else {
while(j<vec2.size()){
vec.push_back(vec2[j]);
j++;
}
}
}
void div(std:: vector<num>&vec){
if(vec.size()<2)return;
std:: vector<num>vec1;
std:: vector<num>vec2;
for(int i(0);i<vec.size()/2;i++)vec1.push_back(vec[i]);
for(int i=vec.size()/2;i<vec.size();i++)vec2.push_back(vec[i]);
div(vec1);
div(vec2);
vec.clear();
merge(vec1,vec2,vec);
}
int main(){
int n;
cin>>n;
std:: vector<num>vec;
while(n--){
int m;
cin>>m;
num temp(m);
vec.push_back(temp);
}
div(vec);
int sum(0);
for(int i(0);i<vec.size();i++){
sum+=vec[i].count;
}
cout<<sum;
return 0;
}
by nculemonlsy123 @ 2019-10-25 16:48:48
我之前写的也是VECTOR,后来改数组过了