求教,关于手写快排的一个神奇问题
  • 板块学术版
  • 楼主HMR202001
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/22 10:32
  • 上次更新2023/10/27 18:58:04
查看原帖
求教,关于手写快排的一个神奇问题
575093
HMR202001楼主2022/7/22 10:32

团队题

(可能并不是那么有用的题意)

题意

有n个人,输入第一行按顺序给出这n个人的智力值,第二行给出体力值。对于一个人A来说,在剩下的人里如果没有人智力值和体力值都比A高,则A就是牛人,请统计牛人的个数

样例

输入

5

25 40 30 20 5

20 10 25 38 5

输出

3

代码(80pts,WA两点)

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n;
struct Node{
	int zl,tl;
}a[N];
bool cmp(Node a,Node b){
	if(a.zl==b.zl) return a.tl>b.tl;
	return a.zl<b.zl;
}
void mysort(int l,int r){
	if(l>=r) return;
	int i=l,j=r;
	Node mid=a[(l+r)/2],t;
	while(i<=j){
		while(i<r&&cmp(a[i],mid)) i++;
		while(j>l&&!cmp(a[j],mid)) j--;
		if(i<=j){
			t=a[i];
			a[i]=a[j];
			a[j]=t;
			i++;
			j--; 
		}
	}
	mysort(l,j);
	mysort(i,r);
}
int main(){
	int cnt=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].zl;
	}
	for(int i=0;i<n;i++){
		cin>>a[i].tl;
	}
	mysort(0,n-1);
	bool b;
	for(int i=0;i<n;i++){
		b=1;
		for(int j=i+1;j<n;j++){
			if(a[j].tl>a[i].tl){
				b=0;
				break;
			}
		}
		if(b){
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
}

当我将代码中第18行的

!cmp(a[j],mid)

改为

cmp(mid,a[j])

的时候,从80分变成了100分

想问一下这是为什么

(不要问我为什么不用sort(),问就是我们老师不让…)

2022/7/22 10:32
加载中...