acd - 1216 - Beautiful People（二維LIS）
來源：程序員人生 發布時間：2014-11-13 08:49:10 閱讀次數：2526次
題意：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
