f608 - 4. 飛黃騰達
題目描述
題目要求計算在二維座標平面上，飛黃最多可以吃到多少個果實，飛黃只能往右上方移動，且果實座標必須是整數。
解題思路
本題可以轉換為求最長遞增子序列 (Longest Increasing Subsequence, LIS) 的問題。首先，按照 x 座標排序果實，如果 x 座標相同，則按照 y 座標排序。排序後，問題就變成了求 y 座標的最長遞增子序列。可以使用二分搜尋優化 LIS 的求解過程，將時間複雜度降低到 O(n log n)。
具體步驟如下：
- 按照 x 座標排序果實。
- 維護一個
lis陣列，用於儲存目前找到的最長遞增子序列的末尾元素。 - 遍歷排序後的果實：
- 如果目前
lis陣列為空，或者當前果實的 y 座標大於等於lis陣列的最後一個元素，則將當前果實的 y 座標添加到lis陣列的末尾。 - 否則，使用二分搜尋在
lis陣列中找到第一個大於或等於當前果實 y 座標的元素，並將該元素替換為當前果實的 y 座標。
- 如果目前
lis陣列的長度即為最長遞增子序列的長度，也就是飛黃最多可以吃到的果實數量。
複雜度分析
- 時間複雜度: O(n log n) (排序 O(n log n)，LIS 計算使用二分搜尋 O(n log n))
- 空間複雜度: O(n) (lis 陣列)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
using namespace std;
struct p{
int x,y;
};
p pt[200001];
int n,lis[200001],it;
inline bool cmp(p xx,p yy){
if(xx.x>yy.x||(xx.x==yy.x&&xx.y>yy.y))return 0;
return 1;
}
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
n=read();
for(int i=0;i<n;++i){
pt[i].x=read();
pt[i].y=read();
}
sort(pt,pt+n,cmp);
for(int i=0;i<n;++i){
if(it==0||pt[i].y>=lis[it-1]){
lis[it]=pt[i].y;
++it;
}
else{
*upper_bound(lis,lis+it,pt[i].y)=pt[i].y;
}
}
write(it);
}