[HOJ] 314 - 圓桌武士

Problem : 314 - 圓桌武士

Problem：

有一張圓桌，上面坐了 n 個武士，每個武士都有唯一一到自己喜歡的菜，他們也都希望可以夾到自己喜歡的菜。

這張桌子上每個人面前也剛好有一道菜，而且每道菜可以被夾無數次。不巧的是，因為禮貌的問題，每個人只能夾在自己面前的那一道菜。然而在每個人面前的菜不一定是自己喜歡的。因此他們必須旋轉圓桌(每次順時針 or 逆時針旋轉一格)來將自己喜歡的菜轉到面前。

每將圓桌順時針或者逆時針旋轉一格需要花 1 單位的時間，請問你至少要花多少時間才能夠讓每個人夾到自己喜歡的菜呢？

Input：

第一行有一個數字 n，代表圓桌上有 n 個武士。
第二行上有 n 個數字，第 i 個數字代表第 i 個武士希望夾到的菜的編號(在 1 到 n 之間)。
第三行上有 n 個數字，第 i 個數字代表第 i 個武士目前面前的菜是哪一道，保證每個武士喜歡的菜都會出現。

40% 的測試資料滿足：n ≤ 2000
所有測試資料滿足： n ≤ 2000000

Output：

輸出一個數字，代表最少需要花多少時間才能讓所有武士夾到自己喜歡的東西。

Sample Input：

5
1 2 3 4 5
5 4 3 2 1

Sample Output：

4

------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct P{
    int L,R;
}s[2000005];
int cmp(P a,P b){ return a.R>b.R;}
int cmp2(P a,P b){ return a.L>b.L;}
int a[2000005],b[2000005],top=0;
vector<int> arr[2000005];
int main(){
    int n,k,p,i,j,ans=99999999,test,l,r,m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++){
        scanf("%d",&b[i]);
        arr[b[i]].push_back(i);
    }
    for(i=0;i<n;i++){
        p=a[i];
        if(b[i]==p) continue;
        if(arr[p].size()==1){
            s[top].L=(i-arr[p][0]+n)%n;
            s[top++].R=(arr[p][0]-i+n)%n;
            continue;
        }
        l=0,k=r=arr[p].size();
        while(l+1!=r){
            m=(l+r)/2;
            if(arr[p][m]>i) r=m;
            else l=m;
        }
        if(l==0 && arr[p][0]>i){
            s[top].L=i+n-arr[p][k-1];
            s[top++].R=arr[p][0]-i;
        }
        else if(arr[p][k-1]<i){
            s[top].L=i-arr[p][k-1];
            s[top++].R=arr[p][0]+n-i;
        }
        else{
            s[top].L=i-arr[p][l];
            s[top++].R=arr[p][l+1]-i;
        }
    }
    sort(s,s+top,cmp);
    /*for(i=0;i<top;i++)
        printf("%d %d\n",s[i].L,s[i].R);*/
    ans=s[0].R;
    test=0;
    for(i=1;i<top;i++){
        test=max(test,s[i-1].L);
        ans=min(ans,s[i].R+test*2);
    }
    sort(s,s+top,cmp2);
    ans=min(ans,s[0].L);
    test=0;
    for(i=1;i<top;i++){
        test=max(test,s[i-1].R);
        ans=min(ans,s[i].L+test*2);
    }
    printf("%d\n",ans);
}