传统排序TLE了,用快排发现了问题
查看原帖
传统排序TLE了,用快排发现了问题
675459
laobacoder楼主2022/2/4 16:52

第56行的递归引用显示program received signal sigsegv

#include <bits/stdc++.h>
using namespace std;
struct person{
	int num;
	int cnt;
	int ability;
}p[1000001];
int n; 
void mysort(struct person p[]);
void mycompare(struct person p[]);
void myswap(int *p1,int *p2);
void q_sort(struct person p[],int l,int r);
int main()
{
	int r,q;
	cin>>n>>r>>q;
	for(int i=0;i<2*n;i++){
		cin>>p[i].cnt;
		p[i].num=i+1;
	}
	for(int i=0;i<2*n;i++){
		cin>>p[i].ability;
	}
	q_sort(p,0,2*n-1);
	for(int i=0;i<r;i++){
		mycompare(p);
		q_sort(p,0,2*n-1);
	}
	mysort(p);
    cout<<p[2*n-q-1].num<<endl;	
return 0;
}
void mysort(struct person p[])
{
    	for(int j=0;j<2*n-1;j++){
			if(p[j].cnt==p[j+1].cnt && p[j].num>p[j+1].num)
			{
			myswap(&p[j].num,&p[j+1].num);
			myswap(&p[j].ability,&p[j+1].ability);
		}
		}
	}	
void q_sort(struct person p[],int l,int r) {
    int i=l,j=r,x=p[(l+r)].cnt;
    while(i<=j) {
        while(p[i].cnt<x) i++;
        while(p[j].cnt>x) j--;
        if(i<=j){
        	myswap(&p[i].cnt,&p[j].cnt);
    		myswap(&p[i].ability,&p[j].ability);
    		myswap(&p[i].num,&p[j].num);
            i++,j--;
        }
    }
    if(l<j) q_sort(p,l,j);
    if(i<r) q_sort(p,i,r);
}
void mycompare(struct person p[]){
	for(int i=0;i<2*n-1;i++){
		if(p[i].ability>p[i+1].ability)p[i].cnt+=1;
		if(p[i].ability<p[i+1].ability)p[i+1].cnt+=1;
		i++;
	}
}
void myswap(int *p1,int *p2){
	int temp;
	temp=*p1;
	*p1=*p2;
	*p2=temp;
}
2022/2/4 16:52
加载中...