小强现在有个物品,每个物品有两种属性和.他想要从中挑出尽可能多的物品满足以下条件:对于任意两个物品和,满足或者.问最多能挑出多少物品.
进阶:时间复杂度,空间复杂度
第一行输入一个正整数.表示有组数据.
对于每组数据,第一行输入一个正整数.表示物品个数.
接下来两行,每行有个整数.
第一行表示个节点的属性.
第二行表示个节点的属性.
输出行,每一行对应每组数据的输出.
2 3 1 3 2 0 2 3 4 1 5 4 2 10 32 19 21
2 3
1 2 2 5 10 19 21 32 这里有两个2是相等的,这时候我们对y求最长上升子序列的结果是4,很明显不符合题意,因为要保证x也严格单调上升1 2 2 5 10 21 19 32 这里我们对x相等的y进行从大到小的排序,这时候结果是3,符合题意,因为x相等如果y是从小到大的话, 有可能统计重复的x, 我们让y降序排列的话就破坏了y单调上升的可能,不会重复统计x;
#include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int N = 123456; int q[N]; // q数组放的是序列长度为len结尾的的最小的y (贪心的做法) // q[len] = min(y),显然我们q[]是一个严格单调上升的数组 // 简单证明一下 假设q[5] >= q[6],那么以长度为6的子序列中的第5个数 y < q[6] 因为是严格上升的子序列嘛 // 因为q[6] <= q[5], 那么y < q[5],这与我们假设q[5]最小矛盾,所以q[6] > q[5]; // 那么问题来了,对于一个y,我们应该把它放到哪个位置呢,这里有个贪心的做法,我们可以把它接到小于当前y的最大的q[i]后面 // 因为q[] 单调上升,q[i]是小于y的最大的数,那么q[i + 1] >= y, 那么q[i + 1]一定可以被更新, q[i + 1] = y; // 具体怎么二分可以看下面的代码 struct Node { int x, y; bool operator< (const Node & t) const { if (x == t.x) return y > t.y; return x < t.x; } }nodes[N]; int main() { int T; cin >> T; while (T -- ) { int n; cin >> n; for (int i = 0; i < n; i++) cin >> nodes[i].x; for (int i = 0; i < n; i++) cin >> nodes[i].y; sort(nodes, nodes + n); memset(q, 0, sizeof q); // 为了结果一定存在,设置一个哨兵 q[0] = -2e9; int len = 0; for (int i = 0; i < n; i++) { int l = 0, r = len; while (l < r) { int mid = (l + r + 1) >> 1; // 若mid符合条件, 那么要找到最大的一定在mid的右边,同时mid也有可能是答案, l = mid if (q[mid] < nodes[i].y) l = mid; // 否则mid不是答案,答案在mid的左边 r = mid - 1; // 边界问题 mid = (l + r + 1) / 2;要上取整,因为有个减一 else r = mid - 1; } len = max(len, r + 1); q[r + 1] = nodes[i].y; } cout << len << endl; } return 0; }
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //T表示有T组数据 int T = sc.nextInt(); for (int i = 1; i <= T; i++) { //n表示有n个物品 int n = sc.nextInt(); //t[i][0]表示第i个物品的x属性,t[i][1]表示第i个物品的y属性, int[][] t = new int[n][2]; int[] nums = new int[n]; for (int j = 0; j < n; j++) { t[j][0] = sc.nextInt(); } for (int j = 0; j < n; j++) { t[j][1] = sc.nextInt(); } //x相同的情况下y更大的排序在前面(不然的话会重复统计相同的x) Arrays.sort(t, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { if(o1[0] > o2[0]) return 1; else if(o1[0] < o2[0]) return -1; else { if(o1[1] > o2[1]) return -1; else if(o1[1] < o2[1]) return 1; else return -1; } } }); for (int j = 0; j < n; j++) { nums[j] = t[j][1]; } int result = longestSubArray(nums); System.out.println(result); } } public static int longestSubArray(int[] nums) { //tails[k] 的值代表长度为k+1子序列 的尾部元素值 int[] tails = new int[nums.length]; // res 为 tails当前长度 int res = 0; for (int num:nums) { int l = 0; //r为数组的长度,而不是length-1,这点要注意 int r = res; while(l < r) { int m = l + (r - l)/2; if(tails[m] < num) l = m + 1; else r = m; } tails[l] = num; if(r == res) res++; } return res; } }
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; struct node{ int x,y; }goods[maxn]; bool cmp(node a,node b){ if(a.x == b.x) return a.y > b.y; return a.x < b.x; } int lengthOfLIS(vector<int>& nums) { int len = 1, n = (int)nums.size(); if (n == 0) { return 0; } vector<int> d(n + 1, 0); d[len] = nums[0]; for (int i = 1; i < n; ++i) { if (nums[i] > d[len] ) { d[++len] = nums[i]; } else { int l = 1, r = len, pos = 0; while (l <= r) { int mid = (l + r) >> 1; if (d[mid] < nums[i]) { pos = mid; l = mid + 1; } else { r = mid - 1; } } d[pos + 1] = nums[i]; } } //for(int i = 1;i <= len;i++) cout<<d[i]<<" ";cout<<endl; return len; } void solve(){ int n; cin>>n; for(int i = 0;i < n;i++){ cin>>goods[i].x; } for(int i = 0;i < n;i++){ cin>>goods[i].y; } sort(goods,goods+n,cmp); vector<int>vec; for(int i = 0;i < n;i++){ vec.push_back(goods[i].y); } //for(int i = 0;i < vec.size();i++) cout<<vec[i]<<" ";cout<<endl; cout<<lengthOfLIS(vec)<<endl; } int main(){ int T; cin>>T; while(T--){ solve(); } return 0; } /* 100 4 1 1 5 5 1 1 2 3 */
核心思路是将X排序,这样就可以在排序好的X对应的Y中,寻找最长的递增不一定连续的子序列了,这样的子序列代表最后的能挑出的最多的物品。时间复杂度为O(nlogn)
import java.io.*; import java.util.*; public class Main{ //排序器,将X从小到大排序,最关键的一步是将相同的X按Y从大到小排序,因为如果按Y从小到大排序, //会导致后面的大的Y覆盖末尾前面的小的Y,这样就不符合贪心算法的尽量保证末尾元素最小的要求了。 private static Comparator<int[]> comparator = new Comparator<int[]>(){ @Override public int compare(int[] o1,int[] o2){ if (o1[0] > o2[0]) return 1; else if (o1[0] < o2[0]) return -1; else { if (o1[1] > o2[1]) return -1; else if (o1[1] == o2[1]) return 0; else return 1; } } }; public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = bf.readLine(); int n = Integer.parseInt(str); for (int i = 0;i < n;i++){ String str1 = bf.readLine(); int m = Integer.parseInt(str1); String[] str2 = bf.readLine().split(" "); String[] str3 = bf.readLine().split(" "); int[][] items = new int[m][2]; for (int j = 0;j < m;j++){ items[j] = new int[]{Integer.parseInt(str2[j]),Integer.parseInt(str3[j])}; } //对数组排序 Arrays.sort(items,comparator); //res保存最长递增子序列的大小。 int res = 1; //用来保存每个长度末尾的Y尽可能小的[x,y]数组。 int[][] dp = new int[m + 1][2]; dp[1] = items[0]; //二分法进行查找此时的Y刚刚好大于哪一个下标的Y,又小于下一个下标的Y,这样更改下一个下标 //的Y,为此时的Y,就可以保证dp数组保存的是末尾可能的最小的Y。这种方法相对于DP寻找最长 //递增子序列,更快,时间复杂度为O(nlogn) for (int j = 1;j < m;j++){ if (dp[res][1] < items[j][1]) dp[++res] = items[j]; else if (dp[res][1] > items[j][1]){ int l = 1,r = res,pos = 0; while (l <= r){ int mid = (l + r) >> 1; if (dp[mid][1] < items[j][1]){ pos = mid; l = mid + 1; }else{ r = mid - 1; } } if (dp[pos][0] != items[j][0]) dp[pos + 1] = items[j]; } } System.out.println(res); } } }
dp方法时间复杂度为O(n^2),但是这题不能通过
import java.io.*; import java.util.*; public class Main{ //排序器,将X从小到大排序,最关键的一步是将相同的X按Y从大到小排序,因为如果按Y从小到大排序, //会导致后面的大的Y覆盖末尾前面的小的Y,这样就不符合贪心算法的尽量保证末尾元素最小的要求了。 private static Comparator<int[]> comparator = new Comparator<int[]>(){ @Override public int compare(int[] o1,int[] o2){ if (o1[0] > o2[0]) return 1; else if (o1[0] < o2[0]) return -1; else { if (o1[1] > o2[1]) return -1; else if (o1[1] == o2[1]) return 0; else return 1; } } }; public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = bf.readLine(); int n = Integer.parseInt(str); for (int i = 0;i < n;i++){ String str1 = bf.readLine(); int m = Integer.parseInt(str1); String[] str2 = bf.readLine().split(" "); String[] str3 = bf.readLine().split(" "); int[][] items = new int[m][2]; for (int j = 0;j < m;j++){ items[j] = new int[]{Integer.parseInt(str2[j]),Integer.parseInt(str3[j])}; } //对数组排序 Arrays.sort(items,comparator); //dp数组保存的是至今这个下标位置,最大的非连续递增序列的长度。 int res = 0; int[] dp = new int[m]; for (int j = 0;j < m;j++){ dp[j] = 1; for (int l = 0;l < j;l++){ if (items[l][0] < items[j][0] && items[l][1] < items[j][1]) dp[j] = Math.max(dp[j],dp[l] + 1); } res = Math.max(dp[j],res); } System.out.println(res); } } }
给个 Python 能过的
from bisect import bisect_left T = int(input()) for _ in range(T): n = int(input()) X = map(int, input().split()) Y = map(int, input().split()) a = sorted(zip(X, Y), key=lambda x: (x[0], -x[1])) total = 0 q = [0] * 100005 for i in range(n): t = bisect_left(a=q, x=a[i][1], lo=0, hi=total) if t == total: total += 1 q[t] = a[i][1] print(total)
假如用了 dataclass 会 TLE
from __future__ import annotations from bisect import bisect_left from dataclasses import dataclass @dataclass class node: x: int y: int def __lt__(self, other: node): if self.x != other.x: return self.x < other.x return self.y > other.y T = int(input()) for _ in range(T): n = int(input()) X = map(int, input().split()) Y = map(int, input().split()) a = sorted(node(*x) for x in zip(X, Y)) total = 0 q = [0] * 100005 for i in range(n): t = bisect_left(a=q, x=a[i].y, lo=0, hi=total) if t == total: total += 1 q[t] = a[i].y print(total)
//最长上升子序列 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int T,N; cin >> T; while((T--) > 0){ cin >> N; vector<vector<int>> XY(N, vector<int>(2)); for(int i = 0;i < N;i++){ cin >> XY[i][0]; } for(int i = 0;i < N;i++){ cin >> XY[i][1]; } //按照x升序排序 sort(XY.begin(), XY.end(), [&](const auto &l, const auto &r){ return (l[0] == r[0])? l[1] > r[1]:l[0] < r[0]; }); //对每个i进行二分查找 //dp[i]表示前i项最后一项 vector<int> dp(N+1); dp[1] = XY[0][1]; int len = 1; for(int i = 1;i < N;i++){ //对每个元素寻找最长递增子序列 if(XY[i][1] > dp[len]){ dp[++len] = XY[i][1]; } else{ int l = 1, r = len, k = 0; while(l <= r){ int mid = (l+r)>>1; //找到小于XY[i][1]的最小dp if(dp[mid] < XY[i][1]){ k = mid; l = mid+1; }else{ r = mid-1; } } dp[k+1] = XY[i][1]; } } printf("%d\n", len); } }[LC.300](https://leetcode-cn.com/problems/longest-increasing-subsequence/)
C++奉上
#include<bits/stdc++.h> using namespace std; //一眼就能看出来是固定一个维度后的最长递增子序列问题,和力扣里的俄罗斯套娃问题、马戏团搭人梯问题类似 int helper(vector<vector<int>>& nums, int n){ sort(nums.begin(), nums.end(), [&](auto& a, auto& b){ if(a[0] == b[0]) return a[1] > b[1]; return a[0] < b[0]; }); //这里用贪心+二分+dp来从O(n2)优化为O(nlogn) vector<int> f; f.push_back(nums[0][1]); for(int i = 1; i < n; i++){ if(nums[i][1] > f.back()) f.push_back(nums[i][1]); else{ auto it = lower_bound(f.begin(), f.end(), nums[i][1]); *it = nums[i][1]; } } return f.size(); } int main(){ int count; cin >> count; while(count-- > 0){ int n; cin >> n; vector<vector<int>> nums(n, vector<int>(2)); for(int i = 0; i < 2; i++){ for(int j = 0; j < n; j++){ cin >> nums[j][i]; } } cout << helper(nums, n) << endl; } }
import java.util.*; public class Main { /** * 阿里1:小强现在有个物品,每个物品有两种属性和.他想要从中挑出尽可能多的物品满足以下条件: * 对于任意两个物品和,满足或者.问最多能挑出多少物品. * 3 * 1 3 2 * 0 2 3 * 输出:2 * 最长递增子序列 */ public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); for(int i=0;i<m;i++){ int n = in.nextInt(); int[][] arr = new int[n][2]; for(int j=0;j<n;j++) arr[j][0] = in.nextInt(); for(int j=0;j<n;j++) arr[j][1] = in.nextInt(); //按x从小到大排序,如果x相等,按y从大到小排序 Arrays.sort(arr, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]; } }); System.out.println(LIS(arr,n)); } } //求最长递增子序列 public static int LIS(int[][] arr,int n){ //dp[i]记录长度为i的递增序列中的最大值 int[] dp = new int[n+1]; int k=1; dp[k] = arr[0][1]; for(int j=1;j<n;j++){ if(arr[j][1]>dp[k]) dp[++k] = arr[j][1];//大于dp[k] k才加,确保dp递增 else { int left = 1; int right = k; int mid = (left+right)/2; while(left<=right){ mid = (left+right)/2; if(arr[j][1]>dp[mid]) left = mid+1; else right = mid-1; } dp[right+1] = arr[j][1];//更新比他小的最大值的下一个,因为下一个一定大于等于他 } } return k; } }
package main import ( "bufio" "fmt" "math" "os" "sort" "strconv" "strings" ) func main() { var a, n int in := bufio.NewScanner(os.Stdin) //设置缓冲区区间,不设置的话会报错 //这里用fmt.Scan()读取一行超长文本时会超时 in.Buffer([]byte{}, 1000000000000) in.Scan() a, _ = strconv.Atoi(strings.Split(in.Text(), " ")[0]) for i := 0; i < a; i++ { in.Scan() n, _ = strconv.Atoi(strings.Split(in.Text(), " ")[0]) q := make([]int, n+1) nodes := make([][]int, n) for j := 0; j < n; j++ { nodes[j] = make([]int, 2) } for j := 0; j < 2; j++ { in.Scan() str := in.Text() //fmt.Println(str) //fmt.Println(len(str)) s := strings.Fields(str) for k := 0; k < n; k++ { nodes[k][j], _ = strconv.Atoi(s[k]) } } //fmt.Println(nodes) sort.Slice(nodes, func(i, j int) bool { if nodes[i][0] == nodes[j][0] { return nodes[i][1] > nodes[j][1] } else { return nodes[i][0] < nodes[j][0] } }) //fmt.Println(nodes) q[0] = -2e9 len := 0 for i := 0; i < n; i++ { l := 0 r := len for l < r { mid := (l + r + 1) >> 1 // 若mid符合条件, 那么要找到最大的一定在mid的右边,同时mid也有可能是答案, l = mid if q[mid] < nodes[i][1] { l = mid } else { r = mid - 1 } } len = int(math.Max(float64(len), float64(r+1))) q[r+1] = nodes[i][1] } fmt.Println(len) //fmt.Println(nodes) } }
def swap(x, y): return y, x n = int(input()) n1 = [[] for i in range(n)] x = [[] for i in range(n)] y = [[] for i in range(n)] for i in range(n): n1[i] = int(input()) x[i] = input().split() y[i] = input().split() for i in range(n): for j in range(n1[i]): x[i][j] = int(x[i][j]) y[i][j] = int(y[i][j]) for i in range(n): for j in range(n1[i]): for k in range(n1[i]-j-1): if x[i][k] > x[i][k+1]: x[i][k], x[i][k+1] = swap(x[i][k], x[i][k+1]) y[i][k], y[i][k+1] = swap(y[i][k], y[i][k+1]) for i in range(n): x1 = x[:] y1 = y[:] j = 0 while j < len(y1[i])-1: if y1[i][j] >= y1[i][j+1]: x1[i].pop(j+1) y1[i].pop(j+1) j = 0 else: j += 1 print(len(x1[i]))
if(i == n - 1 || t[i].x != t[i + 1].x)
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; long long min(long long a, long long b) { return a < b ? a : b; } struct node { long long x, y; }t[100005]; bool cmp(node a, node b) { if(a.x == b.x) { return a.y < b.y; } return a.x < b.x; } int main() { int T,n; cin>>T; while(T--) { cin>>n; long long dp[n]; int maxLen = 0; for(int i = 0; i < n; ++i) { scanf("%lld", &t[i].x); } for(int i = 0; i < n; ++i) { scanf("%lld", &t[i].y); } sort(t, t + n, cmp); int updateLen = 0; int updateOp[n][2];// 0 loc 1 value bool addNew = false; long long minAddNew = -1; for(int i = 0; i < n; ++i) { int l = 0, r = maxLen - 1, aim = 0; while(l <= r) { int mid = (l + r) / 2; if(t[i].y > dp[mid])// ???mid?????????????? { l = mid + 1; aim = mid + 1; } else { r = mid - 1; } } if(aim >= maxLen) { addNew = true; if(minAddNew == -1 || t[i].y < minAddNew) { minAddNew = t[i].y; } } else { updateLen ++; updateOp[updateLen - 1][0] = aim;// 0 loc 1 value updateOp[updateLen - 1][1] = t[i].y; } if(i == n - 1 || t[i].x != t[i + 1].x) { if(addNew) { dp[maxLen++] = minAddNew; addNew = false; minAddNew = -1; } for(int j = 0; j < updateLen; ++j) { dp[updateOp[j][0]] = min(dp[updateOp[j][0]], updateOp[j][1]); } updateLen = 0; } } cout<<maxLen<<endl; } }
import java.util.Scanner; import java.util.Collections; import java.util.Scanner; import java.util.Comparator; import java.util.ArrayList; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int m=in.nextInt(); for(int i=0;i<m;++i) { // 注意 while 处理多个 case int n = in.nextInt(); ArrayList<int[]> property = new ArrayList<>(); for(int j=0;j<n;++j){ property.add(new int[2]); property.get(j)[0]=in.nextInt(); } for(int j=0;j<n;++j){ property.get(j)[1]=in.nextInt(); } Collections.sort(property, new Comparator<int[]>(){ @Override public int compare(int[] a, int[] b){ return a[0]==b[0]?b[1]-a[1]:a[0]-b[0]; } }); int res=0; ArrayList<Integer> stack=new ArrayList<>(); stack.add(property.get(0)[1]); for(int j=1;j<n;++j){ int k=stack.size()-1; if(stack.get(k)<property.get(j)[1]){ stack.add(property.get(j)[1]); continue; } while(k>=0&&stack.get(k)>=property.get(j)[1]){ k--; } stack.set(k+1,property.get(j)[1]); } System.out.println(stack.size()); } } }
class Goods: def __init__(self, x, y): self.x = x self.y = y class LIS: # 求最长上升子序列 def __init__(self, array): self.array = array def find_lis(self): if self.array == []: return -1 dp = [self.array[0].y] for a_idx in range(1, len(self.array)): if self.array[a_idx].y > dp[-1]: dp.append(self.array[a_idx].y) else: bs = BinarySerch(dp, self.array[a_idx].y) idx = bs.serch_by_recursion() dp[idx] = self.array[a_idx].y return len(dp) class BinarySerch: # 二分查找 def __init__(self, ordered_list, target): self.ordered_list = ordered_list self.target = target def serch_by_recursion(self): return self._recursion(0, len(self.ordered_list)-1) def _recursion(self, start, end): # if start > end: # return start if start >= end: if self.target > self.ordered_list[start]: return start+1 else: return start mid = start + (end-start)//2 if self.target > self.ordered_list[mid]: return self._recursion(mid+1, end) elif self.target == self.ordered_list[mid]: return mid else: return self._recursion(start, mid-1) if __name__ == "__main__": group_num = int(input()) res = [] for gn in range(group_num): goods_num = int(input()) goods_x = input() goods_y = input() x_list = list(map(int, goods_x.split())) y_list = list(map(int, goods_y.split())) goods_list = [] for index in range(len(x_list)): goods = Goods(x_list[index], y_list[index]) goods_list.append(goods) goods_list.sort(key=lambda goods: (goods.x, -goods.y)) lis = LIS(goods_list) print(lis.find_lis())
//dp 但是超时了, 2/10 #include<iostream> #include<vector> #include<algorithm> using namespace std; //ruct node{ // int x; //int y; // bool operator<() // int main(){ int k=0; cin>>k; while(k--){ int l=0; cin>>l; //vector<node> res(l,nullptr); vector<pair<int,int>> res(l,pair<int,int>()); for(int i=0;i<l;i++) cin>>res[i].first; for(int j=0;j<l;j++) cin>>res[j].second; sort(res.begin(),res.end(),[](const pair<int,int>& a,const pair<int,int>& b){if(a.first==b.first) return a.second>b.second;return a.first<=b.first;}); vector<int> dp(l,1); //dp[0]=1; int ret=0; for(int i=1;i<l;i++){ for(int j=0;j<i;j++){ if(res[j].second<res[i].second){ dp[i]=max(dp[i],dp[j]+1); } } if(dp[i]>ret) ret=dp[i]; } cout<<ret<<endl; } return 0; }