解题报告

题目

传送门：https://www.luogu.com.cn/problem/CF819B

题意翻译

• 定义一个全排列 p_i 的偏移值为\(\sum_{i=1}^n\)| p_i - i |
• 给你一个全排列，你可以从后面拿k∈[0,n?1]个数放在前面，使得该全排列的偏移值最小，输出这个偏移值和k，如果有多个k任意输出一个
• n ≤ 10⁶

开整

（不看翻译是真的看不懂……）

上来一看以为要用差分，莽一波欢乐报零。于是换个思路想一想。

就暴力而言，我们是从后往前，一个一个拿到最前面，然后再扫一遍判断ans的变化。

于是乎，转念一想，我们当前位的数的本身的大小是不变的，而我们每操作一次它的编号 i 就会增大1 。

那么，对于原先偏移值（注意这个“原”是对于当前次操作而言，而并非是最开始的那个，下面的也是一样，我们的偏移值是在随着操作不断改变的）为正数的，显然对ans的贡献量会减少1，即ans一共会减少原偏移值为正的数的个数。

对于原偏移值为非正的，显然对ans的贡献会加1，所以ans的增加量是原偏移值为非正数的数的个数。

所以，我们要维护的就是原偏移值为正的和非正的数的个数。

然后我们就可以考虑了，经过一次操作，原偏移值为+1的数偏移值都会变为0，也就是说，原偏移值为正数的数的个数会少掉原偏移值为+1的数的个数。

而原偏移值为非正数的数的个数会加上原偏移值为+1的数的个数，这也是显然的。所以原偏移值为非正的数的个数不会变少，只会越来越多。

另外，每次操作我们把第 n-i+1 位的数放到最前面，这个数所带来的偏移值的改变直接计算即可。

这样我们整个时间效率应该是稳定的O(2n)，然后这题最好别用cin，cout...虽然能过，但是我加优化都跑了15s...

然后，就这样。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define ll long long
#define Dio ios::sync_with_stdio(0)
using namespace std;
const int maxn=3e6+10;
int a[maxn];
ll ans=0,k=0;
ll zheng_cnt,fu_cnt;
ll one[maxn];//第i次操作时原偏移值为1的数的个数就是one[i]，大家想一想就知道了。
int main(){
    Dio;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int x=a[i]-i;
        if(x<=0){
            fu_cnt++;
            ans+=abs(x);
        }
        else{
            zheng_cnt++;
            ans+=x;
            one[x]++;
        }
    }
    ll tmp,tmpp=ans;//为了避免错误地修改ans，咱们用两个中间变量跑循环
    if(ans==0){//一些剪枝优化，但感觉没什么卵用
        cout<<0<<" "<<0<<endl;
        return 0;
    }
    for(int i=1;i<n;i++){//没什么好说的了
        tmp=tmpp;
        tmp-=zheng_cnt;
        tmp+=fu_cnt;
        zheng_cnt-=one[i];
        fu_cnt+=one[i];
        
        //对这个挪动的数进行操作
        ll x=a[n-i+1];
        tmp-=n+1-x;
        fu_cnt--;
        if(x>1){
            one[x-1+i]++;
            tmp+=x-1;
            zheng_cnt++;
        }
        else fu_cnt++;
        //操作结束
        
        if(tmp<ans){
            ans=tmp;
            k=i;
        }
        if(ans==0){//还是剪枝，依然是没什么卵用
            cout<<0<<" "<<k<<endl;
            return 0;
        }
        tmpp=tmp;//记得循环一下变量，不然整个过程就不是连续的了
    }
    cout<<ans<<" "<<k<<endl;
    return 0;
}

CF819B Mister B and PR Shifts

原文：https://www.cnblogs.com/Zfio/p/12856355.html