inver-姜.cpp

设计一个算法

#include<iostream>
#include<fstream>
class Inver;
class Info{
    private:
        int m;
        int n;
    public:
        friend class Inver;
};
class Inver{
    private:
        Info *data;
        int size;
        void merge(int low,int mid,int high);
    public:
        Inver(int n){data=new Info[n+1];size=n;}
        ~Inver(){delete []data;}
        void mergesort(int low,int high);
        void Input(std::ifstream &fin);
        void Output(std::ofstream &fout);
};
void Inver::mergesort(int low,int high)
{
    if(low<high){
        int mid=(low+high)/2;
        mergesort(low,mid);
        mergesort(mid+1,high);
        merge(low,mid,high);
    }
}
void Inver::merge(int low,int mid,int high)
{
    int i=low,j=mid+1;
    while(i<=mid && j<=high){
        if(data[i].m<=data[j].m){
            data[j].m-=data[i].m;
            i++;
        }
        else{
            data[i].m-=(data[j].m+1);
            Info temp=data[j];
            int k=j++;
            while(k>i){
                data[k]=data[k-1];
                k--;
            }
            data[i++]=temp;
        }
    }
}
void Inver::Input(std::ifstream &fin)
{
    for(int i=1;i<=size;i++){
        fin>>data[i].m;
        data[i].n=i;
    }
}
void Inver::Output(std::ofstream &fout)
{
    for(int i=1;i<=size-1;i++)
        fout<<data[i].n<<" ";
    fout<<data[size].n<<std::endl;
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"open error"<<endl;
        exit(1);
    }
    int n;
    while(fin>>n){
        Inver inver(n);
        inver.Input(fin);
        inver.mergesort(1,n);
        inver.Output(fout);
    }
    fin.close();
    fout.close();
    return 0;
}