首页 > 代码库 > SGU 199 Beautiful People(DP+二分)
SGU 199 Beautiful People(DP+二分)
时间限制：0.25s
空间限制：4M
题意：
有n个人，每个人有两个能力值，只有一个人的两个能力都小于另一个的能力值，这两个人才能共存，求能同时共存的最大人数。
Solution：
显然这是一个两个关键字的最长上升序列。
先按照第一种能力值为第一关键字从小到大，第二能力值为第二关键字从大到小排序（为什么?）
然后就是直接用O（nlogn）的DP就好了
（排序的方法是根据O（nlogn）DP算法中所用到的辅助数组的性质。。。如果对这个算法理解足够的话应该比较容易想到）
code（要用C++提交）
#include <iostream>#include <algorithm>#include <utility>#include <vector>using namespace std;int n;struct node { int first, second, id;} f[100009];int s[100009], pre[100009];bool cmp (node a, node b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first;}int main() { ios::sync_with_stdio (0); cin >> n; for (int i = 1; i <= n; i++) cin >> f[i].first >> f[i].second, f[i].id = i; sort (f + 1, f + 1 + n, cmp); int ans = 0, t = 1; for (int t = 1; t <= n; t++) { int l = 0, r = ans, last = -1; while (l <= r) { int mid = (l + r) >> 1; if (f[t].second > f[s[mid]].second) { last = mid + 1; l = mid + 1; } else r = mid - 1; } pre[t] = s[last - 1]; if (f[t].second < f[s[last]].second || s[last] == 0) s[last] = t; if (last > ans) ans++; } cout << ans << endl; for (int i = s[ans]; i; i = pre[i]) cout << f[i].id << ‘ ‘;}
SGU 199 Beautiful People(DP+二分)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。