题目描述:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210504162156969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUxMjE5ODE0,size_16,color_FFFFFF,t_70)
原本的思路:
采用两个for循环,按着题目意思,时间复杂度为n2,的得分为85,一部分样例超时了
原本的代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin>>n;
int *a=new int[n];
int *b=new int[n];
int *c=new int[n];
for(long long i=0;i<n;i++){
cin>>a[i]>>b[i];
c[i]=0;
}
int max=0;
int d=0;
for(long long i=0;i<n;i++){
for(long long j=0;j<n;j++){
if(a[i]<=a[j]&&b[j]==1)
c[i]++;
if(a[i]>a[j]&&b[j]==0)
c[i]++;
}
if(c[i]>max){
max=c[i];
d=i;
}
if(c[i]==max&&a[i]>a[d]){
max=c[i];
d=i;
}
}
cout<<a[d]<<"\n";
delete []a;
delete []b;
delete []c;
}
修改之后的思路:
存在超时问题,应该改用,快排+for,此时时间复杂度变为由快排决定的nlogn。
两个单独的for循环分别计算前后成功的情况数值,再进行比较
修改后的代码:
#include<bits/stdc++.h>
using namespace std;
struct node {
int x,y,z;
};
bool cmp(const node &a,const node &b) {
if(a.x !=b.x )
return a.x<b.x ;
return a.y>b.y;
}
int main() {
int n;
cin>>n;
node A[n];
for(int i=0; i<n; i++)
cin>>A[i].x>>A[i].y;
sort(A,A+n,cmp);
int sum=0;
for(int i=0; i<n; i++) {
A[i].z=sum;
if(A[i].y==0)
sum++;
}
sum=0;
for(int i=n-1; i>=0; i--) {
if(A[i].y==1)
sum++;
A[i].z+=sum;
}
int tmp=A[0].z;
int k=0;
for(int i=0;i<n;i++){
if(tmp<=A[i].z){
tmp=A[i].z;
k=A[i].x;
}
}
cout<<k<<endl;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)