P5846题解

· · 题解

其实这道题比较水，果然是远古时期的题我们假设每一名同学都向一个方向移动，此时距离确定，我们发现，如果考虑两个方向，比如有 6 名同学，一个座位到任意座位最近距离有可能有以下情况：

距离 方向
3 某个格子向左和向右均为此数，只有一个
2 向右
2 向左
1 向右
1 向左
0 无

为 n=7 时:

距离 方向
3 向右
3 向左
2 向右
2 向左
1 向右
1 向左
0 无

而当我们指定方向时，就有距离为 0 到 n-1 中的一种，我们发现 \lfloor \frac{n}{2} \rfloor 是临界点，如果值大于它，实际距离就会减小。

当 n=6 时：

特定方向距离 实际距离
0 0
1 1
2 2
3=\lfloor \frac{6}{2} \rfloor 3
4 2
5 1

当 n=7 时：

特定方向距离 实际距离
0 0
1 1
2 2
3=\lfloor \frac{7}{2} \rfloor 3
4 3
5 2
6 1

不难发现我们可以将座位号进行转圈,比如

此时特定距离将同时加或减一个数，超界就循环，比如 $-1\rightarrow n-1$，$n\rightarrow 0$。 但不管怎样，都是离 $\lfloor \frac{n}{2} \rfloor,\lceil \frac{n}{2} \rceil$ 越远越好。 然而，对应 $\lfloor \frac{n}{2} \rfloor$，$\lceil \frac{n}{2} \rceil$ 的特定方向距离，于是我们就用没有对应特定方向距离的同学来对应，而周围的座位也对应，因此我们要求所有特定距离中最长连续的没有同学满足的长度。 由于转座位时，距离会循环，因此我们要特判两边的连续无同学对应的和。 我们再分成偶数和奇数两种情况，进行判断距离。 当然这样你以为就对了么？ 不！你会获得 $66$ 分的好成绩~~作者我第一次提交的成绩，调试了好几遍~~，因为题目中有这句话： `需要注意的是 $p_1$ 可以坐在 $p_n$ 左边也可以坐在 $p_n$ 右边。` 因此我们要把 $p$ 数组倒过来算一遍，输出最小值。 # $CODE 
#include<bits/stdc++.h>
using namespace std;
bool t[1000009];
int a[1000009];
int main(){
    int n;
    int ma;
    int u;
    int x,y;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++){//特定方向距离记录
        t[(a[i]-i+n)%n]=1;
    }
    ma=0;
    u=0;
    for(int i=0;i<n;i++){//算最长连续无同学对应座位
        if(t[i]){
            ma=max(ma,u);
            u=0;
        }else{
            u++;
        }
    }
    ma=max(ma,u);
    u=0;
    for(int i=0;i<n;i++){//特判循环
        if(!t[i]){
            u++;
        }else{
            break;
        }
    }
    for(int i=n-1;i>=0;i--){
        if(!t[i]){
            u++;
        }else{
            break;
        }
    }
    ma=max(ma,u);

    x=n/2;
    if(n%2){//分奇偶情况
        x-=ma/2;
    }else{
        if(ma>0){
            x--;
            ma--;
        }
        x-=ma/2;
    }
    memset(t,0,sizeof(t));//倒过来算
    for(int i=1;i<=n;i++){
        t[(a[n+1-i]-i+n)%n]=1;
    }
    ma=0;

    u=0;
    for(int i=0;i<n;i++){
        if(t[i]){
            ma=max(ma,u);
            u=0;
        }else{
            u++;
        }
    }
    ma=max(ma,u);
    u=0;
    for(int i=0;i<n;i++){
        if(!t[i]){
            u++;
        }else{
            break;
        }
    }
    for(int i=n-1;i>=0;i--){
        if(!t[i]){
            u++;
        }else{
            break;
        }
    }
    ma=max(ma,u);

    y=n/2;
    if(n%2){
        y-=ma/2;
    }else{
        if(ma>0){
            y--;
            ma--;
        }
        y-=ma/2;
    }
    cout<<min(x,y);
    return 0;
}

不难发现这是贪心作者我写到几乎末尾才发现 思路的话我思路不是特别清晰，所以写的特别啰嗦，所以大家主要看代码，思路仅供参考，帮助大家理解，祝大家切题愉快。