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 Si and 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 <= Sj and Bi >= Bj or if Si >= Sj and 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
Output
Sample Input
4 1 1 1 2 2 1 2 2
Sample Output
2 1 4
题意：邀请一堆人参加宴会，每个人的两个值strong and beautiful.必须彼此不相交（就是不能存在Si <= Sj and Bi >= Bj or if Si >= Sj and Bi <= Bj ）问最多邀请多少人，并输出任意解
做法：一眼看到这种邀请不邀请的就想到了最大独立集，QAQ，要不是学弟提醒死活想不到是LIS，然而看着模板不知道怎么用==学弟说是先排第一个升序，再排第二个降序，几经周折改出来了，然而死活卡在输出任意解了，想到“被利用”的才能作为最终结果，还是不知道怎么写。
结束之后搜了题解才知道，需要增加记录的数组值不是i,也不是pos啥的，而是利用了这个值所能达到的最长长度，最终遍历输出的判断条件是新增的数组当前值是否是ans
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[122222],b[100009],f[122222],d[122222],n,len;
int pos[100009];
int fin[100009];
struct node
{
int a,b,pos;
}num[100009];
bool cmp(node x,node y)
{
if(x.a!=y.a)return x.a<y.a;
return x.b>y.b;
}
int find(int x,int len)
{
int mid,left=1,right=len;
while(left<=right)
{
mid=(left+right)>>1;
if(d[mid]==x) return mid;
else if(d[mid]<x) left=mid+1;
else right=mid-1;
}
return left;
}
int solve()
{
d[len=1]=num[1].b;
pos[1]=1;
for(int i=2;i<=n;i++)
{
if(num[i].b>d[len])
{
d[++len]=num[i].b;
pos[i]=len;
// printf("len=%d,pos=%d,d=%d\n",len,pos[len],d[len]);
}
else
{
int tmp=find(num[i].b,len);
d[tmp]=num[i].b;
pos[i]=tmp;
// printf("tmp=%d,pos=%d,d=%d\n",tmp,pos[tmp],d[tmp]);
}
}
return len;
}
int main()
{
//freopen("cin.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++) {scanf("%d%d",&num[i].a,&num[i].b);num[i].pos=i;}
sort(num+1,num+n+1,cmp);
memset(d,0x3f3f3f3f,sizeof(d));
int tmp=solve();
printf("%d\n",tmp);
for(int i=n;i>=1;i--)
{
// printf("i=%d,pos=%d\n",i,pos[i]);
if(pos[i]==tmp)
{
printf("%d",num[i].pos);
if(tmp!=1)printf(" ");
tmp--;
}
}
printf("\n");
}
return 0;
}
京公网安备 11010502036488号