Beautiful People
Special JudgeTime Limit:2000/1000MS (Java/Others)Memory Limit:128000/64000KB (Java/Others)
SubmitStatisticNext Problem
Problem Description
The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Siand beauty Bi. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si<= Sjand Bi>= Bjor if Si>= Sjand Bi<= Bj(if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn’t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).
To celebrate a new 2003 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.
Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.
Input
The first line of the input file contains integer N — the number of members of the club. (2 ≤ N ≤100 000). Next N lines contain two numbers each — Siand Birespectively (1 ≤ Si,Bi≤ 109).
Output
On the first line of the output file print the maximum number of the people that can be invited tothe party. On the second line output N integers — numbers of members to be invited in arbitrary order.If several solutions exist, output any one.
Sample Input
41 11 22 12 2
Sample Output
21 4
题目大意：
从n个人中挑选出若干人，使得这些人中的任何一个人的两种属性同时大于或同时小于其他人。输出最多能挑选出的人的个数和编号。解题思路：问题可以化成从这n个人中挑选出若干人，使得他们的两种属性都上升。所以题目就变成了二路最长上升子序列。首先先按照s值为第一关键字（升序），b值为第二关键字（降序）的方式排序。这样排序之后我们可以保证s值一定是升序，所以只需要求出b值的最长上升子序列即为最终答案。b值为什么要按照降序排列呢？因为这样可以最大限度的使得第i个人的b值与经过挑选之后的第i个人的前一个人的b值相差最大。题目的n很大，所以不能使用LIS朴素的O(n^2)的方法，要用O(nlog(n))。同时O(nlog(n))的算法中的dp数组刚好可以记录第i个人之前（包含i）的LIS。最后逆序遍历输出编号。
参考代码：
#include<bits/stdc++.h>using namespace std;const int INF=0x3f3f3f3f;const int MAXN=1e6+50;struct person{int s,b,id;bool operator<(const person& t)const{if(s==t.s)return b>t.b;return s<t.s;}}p[MAXN];int n,dp[MAXN],LIS[MAXN];int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEwhile(scanf("%d",&n)!=EOF){memset(dp,INF,sizeof(dp));memset(LIS,0,sizeof(LIS));int len=1,ans=1;for(int i=1;i<=n;i++){scanf("%d%d",&p[i].s,&p[i].b);p[i].id=i;}sort(p+1,p+1+n);for(int i=1;i<=n;i++){int tid=lower_bound(dp+1,dp+1+len,p[i].b)-dp;if(tid==len)len++;dp[tid]=p[i].b;LIS[i]=tid;ans=max(ans,tid);}printf("%d\n",ans);for(int i=n;i>=1;i–){if(LIS[i]==ans){printf("%d",p[i].id);if(len!=1)printf(" ");ans–;}}puts("");}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
最好的节约是珍惜时间，最大的浪费是虚度年华。
