拼多多 0420机考

第一题 k路字符串 优先级队列
第二题 裸的拓扑排序，注意判断是否有环
第三题 一开始直接写的最长上升子序列（严格），WA，于是推断山的高度必须是整数，于是对nums[i]-i求最长上升子序列（不严格）AC
第四题 样例过，提交之后过0%样例，没看出来哪里错了，贴一下代码
 #include 
using namespace std;

int main() {
    //数据范围来说，至少是需要n方或者更好的算法
    //注意读题，首先不是严格大于，其次需要注意交换需要前提条件，即a[i] > x，这意味着交换过程中,x的数值是原来越大的，和x交换的值的门槛也是越来越大,隐含的条件就是如果小于x的数字没有有序，那么久没办法完成操作了
    //手玩一下：
    //81 324 218 413 324 x = 18 如果与i>=1的位置交换，剩下的18没人可以换走，直接不可行
    //18 324 218 413 324 x = 81 同理，如果与i >= 2的位置交换，剩下的81没有可以换走，直接不可行
    //18 81 218 413 324 x = 324 我们选择将413与324交换
    //18 81 218 324 324 

    //再来领悟一下样例
    //0 2 3 5 4 x = 1 当前发现后面有一个4在捣乱，我们要想办法把它调整下来，但是要调整，就说明当前x = 1需要换上去到某一个位置，也就只能是和2换，这一步是固定的
    //0 1 3 5 4 x = 2 同样的，捣乱的4还没有解决，所以继续要调整，当前x = 2只能换在begin，故而
    //0 1 2 5 4 x = 3 begin变成了5的下标
    //0 1 2 3 4 x = 5 此时发现已经解决

//再来领悟一下输出-1的样例
    //11 9 x = 10 当前begin = 0 end = 1,但是注意到nums[end] < x，最终不可以被移动，所以已经寄了

    //以上过程说明：对于小于x的内容，如果是已经有序地位于开头，那么就已经不可行了
    //对于大于x的无序的内容，如果存在多个，比如10 20 30 40 6 4 x= 3，其中6和4都是乱序的，但似乎此时并不需要决定和其中的谁交换，只能从begin开始交换
    //3 20 30 40 6 4 x = 10
    //3 10 30 40 6 4 x = 20
    //3 10 20 40 6 4 x = 30
    //3 10 20 30 6 4 x = 40 爆炸

    //至此大胆提出假设：先处理得到其中单增的区间
    //0 2 3 5 4 x = 1
    //其中比x小的部分已经确保落在该有的位置上了
    //0 [2 3 5] [4] x = 1 那么我们会把{[2, 3, 5] x = 1}变化为{[1 2 3] x = 5}，即相当于原来有序的空间中最大的没了，最小的变成原有x。花费是有序空间大小
    //然后x变成了原有空间中最大的那个，然后继续这样扫描

//再来手玩一下：
    //4 5 6 7 8 9 10 3 x = 1 
    //{[4 5 6 7 8 9 10] x = 1}->{[1 4 5 6 7 8 9] x = 10} 由于次大的9还是大于无序的3，所以没办法

    //总结思路：线性扫描，找到从开始到现在最长的有序集（其中小于x的部分不统计长度）
int t;
    cin>>t;
    while(t--)
    {
        int n, x;
        cin>>n>>x;
        vector nums(n);
        for (int i = 0; i < n; ++i) cin>>nums[i];

        int begin = 0, end = 0, costBegin = -1;
        int ans = 0;
        bool flag = true;
        while(begin < n)
        {
            //end begin costBegin x ans
            while(end + 1 < n &amp;&amp; nums[end + 1] >= nums[end])//扫描到end，并更新end
            {
                if (costBegin == -1 &amp;&amp; nums[end] > x) costBegin = end;
                ++end;
            }

            // cout<<&quot;begin = &quot;<<<&quot;, end = &quot;<<<&quot;, costBegin = &quot;<<<'\n';
            //从begin 到 end 递增，且从costBegin开始大于x
            if (end == n - 1) break;
            if (begin != end)
            {
                if (nums[end + 1] < nums[end - 1]) {flag = false; break;}//没办法调整
                ans += (end - costBegin + 1);
                x = nums[end];
                end = begin = end + 2;
                costBegin = -1;
            }
            else
            {
                if (nums[end] > x &amp;&amp; x <= nums[end + 1]) {++ans; x = nums[end]; end = begin = end + 2; costBegin = -1;}
                else {flag = false; break;}
            }
        }
        if (flag) cout<<<'\n';
        else cout<<&quot;-1\n&quot;;
    }
    return 0;
}