E. The Contest(调整成递增序列)

https://codeforces.com/problemset/problem/1257/E


思路:lis二分板子

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn],b[maxn],c[maxn],d[maxn],tot=0;
LL ans[maxn],cnt=0;
int main(void){
   cin.tie(0);std::ios::sync_with_stdio(false);
   LL k1,k2,k3;cin>>k1>>k2>>k3;
   for(LL i=1;i<=k1;i++) cin>>a[i];
   for(LL i=1;i<=k2;i++) cin>>b[i];
   for(LL i=1;i<=k3;i++) cin>>c[i];
   sort(a+1,a+1+k1);sort(b+1,b+1+k2);sort(c+1,c+1+k3);
   for(LL i=1;i<=k1;i++) d[++tot]=a[i];
   for(LL i=1;i<=k2;i++) d[++tot]=b[i];
   for(LL i=1;i<=k3;i++) d[++tot]=c[i];

   for(LL i=1;i<=tot;i++){
       LL pos=lower_bound(ans+1,ans+1+cnt,d[i])-ans;
       pos=max(pos,(LL)1);
       if(pos>cnt) cnt++,ans[cnt]=d[i];
       else ans[pos]=d[i];
   }

   cout<<(tot-cnt)<<"\n";
   return 0;
}

 

上一篇:WPF-MVVMLight框架学习--使用MVVMLight


下一篇:一种清晰, 便于扩展android项目架构方案,androidstudio基础教程