序

【問題背景】

zhx 給他的妹子們排序。

【問題描述】

\(zhx\) 有 \(N\) 個妹子， 他對第 \(i\) 個妹子的好感度為\(a_i\), 且所有\(a_i\),兩兩不相等。 現在 \(N\) 個妹子隨意站成一排， 他要將她們根據好感度從小到大排序。 他使用的是冒泡排序算法（詳見下）。如果排序過程中好感度為\(a_i\)的妹子和好感度為\(a_j\)的妹子發生了交換， 那么她們之間會發生一場口角。

現在 \(zhx\) 想知道， 給定妹子的初始排列， 在排序完成后， 最多存在多少個妹
子， 她們任意兩人之間沒發生過口角。

---

冒泡排序有一個特點：第i次使得第i大/小的數歸位。同時大的數不會和小的數交換位置

根據這個特點，我們就知道如果一個子序列是遞增的，那么都不會進行交換。

所以這個題我們求一個最長上升子序列就可以了。

將問題轉化為模型后就是模板le

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using std::min; const int maxn=101000; int length[maxn]; int mf; void ins(int val) {int l=1,r=mf+1;while(l<r){int mid=(l+r)>>1;if(length[mid]>val)r=mid;elsel=mid+1;}if(l==mf+1){length[l]=val;mf++;}else length[l]=min(length[l],val); } int main() {memset(length,100,sizeof(length));int n;scanf("%d",&n);int a;for(int i=1;i<=n;i++){scanf("%d",&a);ins(a);}printf("%d",mf); }

轉載于:https://www.cnblogs.com/Lance1ot/p/9378212.html

總結

以上是生活随笔為你收集整理的序（不知道是什么时候的模拟题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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