acd - 1216 - Beautiful People（二维LIS）
来源：程序员人生 发布时间：2014-11-13 08:49:10 阅读次数：2355次
题意：1个人有两个属性S, B(1 ≤ Si, Bi ≤ 10^9)，当两个人的这两个属性满足 S1 < S2 && B1 < B2 或 S1 > S2 && B1 > B2 时，这两个人不会讨厌对方。现给出 N 个人(2 ≤ N ≤ 100 000)的属性，求最多能有多少个人，他们之间任意两人都不会讨厌对方。
题目链接：http://acdream.info/problem?pid=1216
――>>容易想到是1个2维的LIS模型。。
2维降1维，控制其中1维递增，对另外一维求LIS。。（主要是在排序的时候，让第1维从小到大排，第2维从大到小排，那末，排序后对第2维求LIS的结果肯定不会出现其中的元素对应的第1维是相同的，由于相同的第1维对应的第2维是递减的，而对第2维求LIS是严格递增的。。）
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::sort;
using std::lower_bound;
const int MAXN = 100000 + 10;
const int INF = 0x3f3f3f3f;
struct PERSON
{
int id;
int S;
int B;
bool operator < (const PERSON& e) const
{
return S < e.S || (S == e.S && B > e.B);
}
} person[MAXN];
int N;
int buf[MAXN];
int lis[MAXN], who[MAXN], fa[MAXN], cnt;
int LIS()
{
int ret = 1;
memset(lis, 0x3f, sizeof(lis));
memset(fa, ⑴, sizeof(fa));
who[0] = ⑴;
for (int i = 1; i <= N; ++i)
{
int id = lower_bound(lis + 1, lis + 1 + N, buf[i]) - lis;
lis[id] = buf[i];
who[id] = i;
fa[i] = who[id - 1];
if (id > ret)
{
ret = id;
}
}
return ret;
}
void Read()
{
for (int i = 1; i <= N; ++i)
{
scanf("%d%d", &person[i].S, &person[i].B);
person[i].id = i;
}
}
void Init()
{
sort(person + 1, person + 1 + N);
for (int i = 1; i <= N; ++i)
{
buf[i] = person[i].B;
}
}
void Output(int x)
{
if (fa[x] == ⑴)
{
printf("%d", person[x].id);
return;
}
Output(fa[x]);
printf(" %d", person[x].id);
}
void Solve()
{
cnt = LIS();
printf("%d
", cnt);
Output(who[cnt]);
puts("");
}
int main()
{
while (scanf("%d", &N) == 1)
{
Read();
Init();
Solve();
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
