牛牛找工作（排序）

题目没有给出时间范围，第一次写出之后T了。
题目链接
下面是超时做法：时间复杂度为O(mn)

#include 
using namespace std;
int N,M;
#define LL long long 
typedef pair<LL,LL> PII;pair<LL ,LL > a[100005];
pair<LL,LL> b[100005];
bool cmp(PII a,PII b)
{return a.second>b.second;
}
int main()
{cin>>N>>M;for(int i=0;i<N;i++){cin>>a[i].first>>a[i].second;}sort(a,a+N,cmp);for(int i=0;i<M;i++){cin>>b[i];for(int j=0;j<N;j++){if(b[i]>=a[j].first){cout<<a[j].second<<endl;break;}else if(j==N-1)cout<<0<<endl;             }}return 0;
}

经过改进后复杂度变为O(m),可以通过所有测试用例（其实不需要LL）

#include 
#include 
#include 
using namespace std;
int N,M;
#define LL long long 
typedef pair<LL,LL> PII;pair<LL ,LL > a[100005];
pair<LL,LL> b[100005];
bool cmp(PII a,PII b)
{return a.second<b.second;
}
bool cmp1(PII a,PII b)
{return a.first<b.first;
}
int main()
{cin>>N>>M;for(int i=0;i<N;i++){cin>>a[i].first>>a[i].second;}sort(a,a+N,cmp1);for(int i=0;i<M;i++){cin>>b[i].first;b[i].second=i;}sort(b,b+M,cmp1);int j=0;LL maxmum=0;for(int i=0;i<M;i++){while(j<N){if(a[j].first>b[i].first)break;maxmum=max(maxmum,a[j].second);j++;}b[i].first=maxmum;}sort(b,b+M,cmp);for(int i=0;i<M;i++){cout<<b[i].first<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！