Codeforces Round #743 (Div. 2) B. Swaps 思维

深碍√TFBOYSˉ_ 2022-09-14 06:27 119阅读 0赞

题目地址[Codeforces Round \#743 (Div. 2) B. Swaps][Codeforces Round _743 _Div. 2_ B. Swaps]  
题意很好懂,这里就不复述了。  
**思路**：因为是要让a小于b，所以可以用双指针，在b数组中找到第一个大于a数组中第i个值的数，假定该数的位置为j,则他们的交换次数为i+j，但是由于a数组不是单调序列，所以每一次找b数组都要从头开始，这就会超时，所以可以先把a数组从小到大排列，这样就可以不用从头遍历b数组，因为j前面没有大于a\[i\]的数，就一定没有大于a\[i+1\]的数。  
**错误点**：ap\[N\]这个数组本来是用来存储a数组的值得位置的，a数组的值得范围是\[1,2n\]但是我只开了N,应该开2N的空间的，导致数组越界了。。。关键是cf居然没有数组越界提示。。。。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e5+5;
    int a[N],b[N],ap[N<<1];
    void solve()
    { 
        int n;
        scanf("%d",&n);
        int ans = 2e6;
        for(int i = 0;i < n;i++)
        { 
            scanf("%d",a+i);
            ap[a[i]]=i;
        }
        for(int i = 0;i < n;i++)
        { 
            scanf("%d",b+i);
        }
        sort(a,a+n);
        for(int i = 0,j=0;i < n;i++)
        { 
            while(a[i]>b[j])j++;
            ans=min(ans,ap[a[i]]+j);
        }
        printf("%d\n",ans);
    }
    
    int main()
    { 
    	freopen("in.txt","r",stdin);
    	freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

还有一点思路上的问题，一开始我是这么想的，遍历a数组，然后每次只计算比之前遍历过的a的值小的值，因为比之前找过的比a大的值不需要找，交换次数必然不是最小的，于是我写出了这样的代码：

/* ** */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 1e5+5;
    int a[N],b[N];
    void solve()
    { 
        int n;
        scanf("%d",&n);
        int ans = 2e6;
        for(int i = 0;i < n;i++)
        { 
            scanf("%d",a+i);
        }
    
        for(int i = 0;i < n;i++)
        { 
            scanf("%d",b+i);
        }
    
        int t=1e6;//当前查询过的最小值
        for(int i = 0;i < n&&i<ans;i++)
        { 
            if(a[i]<t)
            { 
                t = a[i];
                for(int j = 0;j < n;j ++)
                { 
                    if(b[j] > a[i])
                    { 
                        ans = min(ans,i+j);
                        break;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

于是我就超时了。。。  
我感觉是因为虽然缩小了查找的范围，但是b数组还是要从头开始，也就是说最坏的情况下复杂度还是 O ( n 2 ) O(n^2) O(n2),好吧，我承认我有赌的成分，但是前面AC的做法就不一样了，将a数组中值的位置记录下来，对其进行排序，这样无论是对a还是对b都是只需要一次遍历即可。（我怎么就没想到呢。。。）

[Codeforces Round _743 _Div. 2_ B. Swaps]: https://codeforces.com/contest/1573/problem/B