題意：
有n個人每人有一個力氣值Si,美麗值Bi，滿足Bi>Bj&&Si>Sj 或者 Bi<Bj&&Si<Sj 的人可以
一起參見晚會，問最多有多少人可以一起參見晚會。
思路： 我們根據S從小到大將所有人排序，然后看B最長的上升子序列的長度求出來即可！
在排序中優先對S排序，S相等的則對B進行由大到小的排序，why？
也就是對于S相同的，我們先選取B最大的值插入LIS中，因為比如 S1=1, B1 = 1
S1=1, B1 = 2, S1=1, B1 = 3, 如果不進行排序，直接按照求B中的lis，顯然長度
為3，顯然是不對的，因為相同的S中只能選擇一個B出來！所以就要對S相同的B進行
降序排序！ 這樣就變成了一個裸lis！

1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdio> 6 #define N 100005 7 using namespace std; 8 9 struct node{ 10 int x, y; 11 int p; 12 }; 13 14 bool cmp(node a, node b){ 15 if(a.x == b.x) 16 return a.y > b.y; 17 return a.x < b.x; 18 } 19 20 bool myCmp(node a, node b){ 21 return a.y <= b.y;//這里要寫成 <=；因為upper_bound返回的是“元素值 >插入值” 22 //最后一個插入值的位置，元素值 == 插入值的時候，默認 元素值 23 // >插入值，但在該題中，相等的情況下不能算在lis中的！ 24 } 25 26 node a[N]; 27 node c[N]; 28 29 int pre[N], path[N]; 30 31 int main(){ 32 int n; 33 while(scanf("%d", &n) != EOF){ 34 for(int i=0; i<n; ++i) 35 scanf("%d%d", &a[i].x, &a[i].y), a[i].p = i+1; 36 37 sort(a, a+n, cmp); 38 c[0] = a[0]; 39 pre[0] = 0; 40 path[0] = 0; 41 int len = 1; 42 43 for(int i=1; i<n; ++i){ 44 int k = upper_bound(c, c+len, a[i], myCmp) - c; 45 pre[i] = k ? path[k-1] : 0;//當前插入節點i的位置為k，它的前一個（k-1位置）元素的序號！ 46 path[k] = i;//當前插入k位置的節點的序號 47 c[k] = a[i]; 48 if(k+1 > len) len = k+1; 49 } 50 int tmp = path[len-1]; 51 printf("%d\n", len); 52 printf("%d", a[path[len-1]].p); 53 for(int i=len-2; i >= 0; --i){ 54 tmp = pre[tmp]; 55 printf(" %d", a[tmp].p); 56 } 57 printf("\n"); 58 59 } 60 return 0; 61 } View Code

?

轉載于:https://www.cnblogs.com/hujunzheng/p/4004777.html

總結

以上是生活随笔為你收集整理的AC_Dream 1216 G - Beautiful People的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。