#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const int N=1e4+10; const int INF=0x3f3f3f3f; int n; struct node { int n,s; }a[N]; bool cmp(node a1,node a2) { return a1.n<a2.n; } int dp[N]; int len; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].n>>a[i].s; } sort(a+1,a+n+1,cmp); dp[++len]=a[1].s; for(int i=2;i<=n;i++) { if(dp[len]<a[i].s) dp[++len]=a[i].s; else { int pos=lower_bound(dp+1,dp+len+1,a[i].s)-dp; dp[pos]=a[i].s; } } cout<< len;

return 0;

}

#include<bits/stdc++.h> using namespace std; int cmp(int a,int b) { return a>b; } int a[100000]; int main() { int n,sum=1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } }

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define LL long long
const int N=1e4+10;
const int INF=0x3f3f3f3f;
int n; 
struct node
{
	int n,s;
}a[N];
bool cmp(node a1,node a2)
{
	return a1.n<a2.n;
}
int dp[N];
int len;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].n>>a[i].s;
	}
	sort(a+1,a+n+1,cmp);
	dp[++len]=a[1].s;
	for(int i=2;i<=n;i++)
	{
		if(dp[len]<a[i].s)
			dp[++len]=a[i].s;
		else
		{
			int pos=lower_bound(dp+1,dp+len+1,a[i].s)-dp;
			dp[pos]=a[i].s;
		}
	}
	cout<< len;
	
	return 0;
}

这题的数据疑似有问题！

毕竟，我debug了1个多小时都没debug出来，但是，当我最后不用$n-maxn$时，居然a了

什么意思呢，就是说，他从求有多少条线要换地方变成了求最长不下降子序列。

所以说，这题只有给你的那1个测试样例是对的，其他都变成求最长不下降子序列了，这也是为什么一题模板能难度到8

本题的accode

#include<bits/stdc++.h>
using namespace std;
struct uuu{
	long long c,d;
};
bool cmp(uuu a,uuu b)
{
	return a.c<b.c;
}
long long dp[100005];
int main()
{
	long long n;
	cin>>n;
	uuu a[n+1];
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i].c>>a[i].d;
	}
	sort(a+1,a+1+n,cmp);
	long long maxn=-1;
	for(long long i=1;i<=n;i++)
	{
		dp[i]=1;
		//cout<<a[i].d<<"\n";
		for(long long j=1;j<i;j++)
		{
			if(a[i].d>=a[j].d)
			{
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		maxn=max(maxn,dp[i]);
	}
	cout<<maxn;
}

但是，如果把输出改成$n-maxn$才是真正的把这题要表达的a了

老师改一下数据吧

少量huhe语言，不影响看。

//#include<huhe>
#include<iostream>
#include<algorithm>
#define h using
#define uh namespace
#define e std
h uh e; //致敬huhe
int n,dp[200010],ans;
struct node{
	int l,r;
}a[200002];
bool cmp(node x,node y){//排序判断用
	return x.l>y.l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+n+1,cmp);//排序
	int len=1;
	dp[1]=a[1].r;
	for(int i=2;i<=n;i++){
		if(a[i].r<dp[len])dp[++len]=a[i].r;
		else{
			int pos=upper_bound(dp+1,dp+1+len,a[i].r,greater<int>())-dp;//用二分找
			dp[pos]=a[i].r;
		}
	}
	cout<<len<<endl;
}
/*
           ,
          / \
         {   }
         p   !
         ; h ;
         | u |
         | h |
         l e l
         l 之l
         H剑 H
         H ; H
         H ; H
         H ; H
         d | b
         U | E
         U | E
         U I E
 ,;,     U I E     ,;,
;H@U;    ;_H_;,   ;H@E;
`\H/u_,;|HU@HE|;,_e\H/'
 '\;HHUUU$@@@$HHEEE;/'
   "~~~*;!h@h!;*~~~"
         ;u8u;
         ;h8h;
         ;e8e;
         ;h8h;
         du@ub
         Oh@hO
         Te0eT
          `~`
*/

没错，注释加了跟没加一样，那是因为我也看不懂我之前写的代码