关于我nlogn却RE这回事
查看原帖
关于我nlogn却RE这回事
540177
wyf_sinon楼主2021/10/20 22:46

有dalao能告诉我 为什么我的nlodn算法会RE吗 自己下样例都输入不完 下面是我的代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],dp[100010],bo[100010],sted,steed,flag;
long long n;
int main() {
	while(cin>>a[++n]) steed=1;
	n--;
	dp[0]=1e4;
	bo[1]=1e4;
	for(int i=1; i<=n; i++) {
		if(a[i]<=dp[sted])	dp[++sted]=a[i];
		else {
			int L=1,R=sted,k=a[i],len;
			while(L<=R) {
				int mid=(L+R)/2;
				if(k<=dp[mid]) {
					L=mid+1;
				} else {
					len=mid;
					R=mid-1;
				}
			}
			dp[len]=k;
		}
	}
	for(int i=1; i<=n; i++) {
		flag=0;
		for(int j=1; j<=steed; j++) {
			if(a[i]<=bo[j]) {
				bo[j]=a[i];
				flag=1;
				break;
			}
		}
		if(flag==0) {
			bo[++steed]=a[i];
		}
	}
	cout<<sted<<endl<<steed;
}
2021/10/20 22:46
加载中...