RE+TLE求救

P1908 逆序对

chenmou2012 @ 2024-03-10 19:52:26

#include<bits/stdc++.h>
using namespace std;

long long ans=0;
vector<int> vmerge;
void PrintVector(const vector<int>& vi){
    for(auto i:vi){
        cout<<i<<" ";
    }
}

void merge(vector<int>& vi,int f1,int l1,int f2,int l2){
    vmerge.resize(0);
    int start = f1;
    while(f1<=l1 && f2<=l2){
        if(vi[f1]<=vi[f2]){
            vmerge.push_back(vi[f1]);
            f1++;
        }else{
            vmerge.push_back(vi[f2]);
            f2++;
            ans+=l1-f1+1;
        }
    }
    if(f1<=l1){
        for (int i = 0; i <= l1; ++i) {
            vmerge.push_back(vi[i]);
        }
    }
    if(f2<=l2){
        for (int i = 0; i <= l2; ++i) {
            vmerge.push_back(vi[i]);
        }
    }
    for (int i = 0; i < vmerge.size(); ++i) {
        vi[start+i] = vmerge[i];
    }
}
void MergeSort(vector<int>& vi,int f,int l){
    int size;
    int ls;
    int n=vi.size();
    for (size = 1;  size<=n-1; size*=2) {
        for(ls=0;ls<n-1;ls+=2*size){
            int mid=min(ls+size-1,n-1);
            int rm = min(ls+2*size-1,n-1);
            merge(vi,ls,mid,mid+1,rm);
        }
    }
}
int main(){
    srand(time(0));
    vector<int> vi;
//    int n;cin>>n;
//    for(int i=0;i<n;i++){
//        int tmp;cin>>tmp;
//        vi.push_back(tmp);
//    }
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int tmp;cin>>tmp;
        vi.push_back(tmp);
    }
    MergeSort(vi,0,vi.size()-1);
    cout<<ans;
    return 0;
}

by Sacred_Konnyaku_mMr @ 2024-03-10 20:46:16

把输入方式调快一点(cin换scanf)

把vector换成普通数组吧


|