codeforces 1257E The Contest（lis）

题意：3堆数，要求使得第一堆的数为前缀，第三堆数为后缀，第二堆数为剩下的数，要求最少调整多少个数的位置使得要求成立。

其实就是就把a1,a2,a3排个序然后拼成一个数组，问题转为一个串需要多少次交换数字变成上升了，那就是n-最长上升子序列了

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const int N = 200005;
int i,j,k;
int cnt,temp,pos;
int n,m;
int x,y,z;
int a[200005],b[200005],c[200005];
int ans,pos1,pos2;
int res1[200005],res2[200005],g[200005];
int main()
{
    scanf("%d %d %d",&x,&y,&z);
    ans=n=x+y+z;
    for(i=1; i<=x; ++i)
        cin>>a[i];
    for(i=1; i<=y; ++i)
        cin>>b[i];
    for(i=1; i<=z; ++i)
        cin>>c[i];
    sort(a+1,a+x+1);
    sort(b+1,b+y+1);
    sort(c+1,c+z+1);
    pos1=1;
    res1[0]=x;
    for(i=1; i<=n; ++i)
    {
        if(a[pos1]==i)
            pos1++;
        res1[i]=i-pos1+1+x-pos1+1;
    }
    pos1=z;
    pos2=y;
    res2[n+1]=z;
    g[n+1]=z;
    for(i=n; i>0; --i)
    {
        if(c[pos1]==i)
            pos1--;
        else if(b[pos2]==i)
            pos2--;
        res2[i]=pos1+y-pos2;
        g[i]=min(res2[i],g[i+1]);
    }
    for(i=0; i<=n; ++i)
        ans=min((ll)ans,(ll)(res1[i]+g[i+1]-(lower_bound(c+1,c+z+1,i)-c-1)));
    printf("%d\n",ans);
    return 0;
}