小石的妹子

第一行输入一个正整数 n，表示妹子的数量。
接下来 n 行，每行两个正整数 $a_i,b_i$ ，描述每个妹子的细心程度和热心程度。
保证所有的 $a_i$ 两两不等，所有的 $b_i$ 两两不等。

C++14(g++5.4) 解法, 执行用时: 278ms, 内存消耗: 3196K, 提交时间: 2019-07-13 21:46:18

#include<bits/stdc++.h>
using namespace std;
struct A{
int a,b,i,m;
}a[100020];
int g[100020],d[100020],n,i,x;
bool cmp(A a,A b){return a.b>b.b;}
int main(){
    cin>>n;
    for(i;i<n;++i)cin>>a[i].a>>a[i].b,a[i].a=-a[i].a,a[i].i=i;
    sort(a,a+n,cmp);memset(g,0x3f3f3f3f,sizeof(g));
    for(i=0;i<n;++i)g[x=lower_bound(g,g+n,a[i].a)-g]=a[i].a,d[a[i].i]=x+1;
    for(i=0;i<n;i++)cout<<d[i]<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 414ms, 内存消耗: 5084K, 提交时间: 2019-07-16 15:19:33

#include<bits/stdc++.h>
using namespace std;
const int N=100020;
int g[N],d[N],n,i,x;
struct A
{
	int a,b,i,m;
	bool operator<(A B)
	{return b>B.b;}
}a[N];
int main()
{
	cin>>n;
	for(i=0;i<n;++i)
		cin>>a[i].a>>a[i].b,a[i].a=-a[i].a,a[i].i=i;
	sort(a,a+n);
	memset(g,0x3f,sizeof g);
	for(i=0;i<n;++i)
		g[x=lower_bound(g,g+n,a[i].a)-g]=a[i].a,d[a[i].i]=x+1;
	for(i=0;i<n;i++)
		cout<<d[i]<<endl;
}

详情